Python排序算法-选择排序

选择排序，顾名思义，就是选出一个元素，通过与剩余元素进行比较，找出最大（最小）的元素，然后进行互相交换。

• 算法实现

通过两层循环遍历实现：

• 列表的长度为n，即列表所有元素的表示范围为：[0,n-1]
• 外层循环i从0开始，到列表倒数第二个，即[0,n-1-1]，因为是从这里取出一个元素，与后面的元素相比较（即无须取最后一个元素，最后一个元素与谁比呢^_^），且前面的元素都排序了，最后一个必然是最大或最小的元素；所以for循环的表示方法为range(n-1)
• 内层循环j从i+1开始，到列表最后一个元素，即[i+1,n-1]，即i与i+1相比，直到最后一个元素[n-1]。所以for循环的表示方法为range(i + 1, n)

# 选择排序算法
# 重点是注意列表下标的取值范围，两轮循环的取值最末端是不同的。
def selection_sort(nums: list[int]):
    n = len(nums)
    # n-1实际取值是n-2位置
    for i in range(n - 1):
        # k记录列表i+1至n-1之间最小数的效标
        k = i
        for j in range(i + 1, n):
            # 在i+1至n-1中发现比num[i]小的数，k记录此下标
            if nums[j] < nums[k]:
                k = j
        nums[i], nums[k] = nums[k], nums[i]


if __name__ == "__main__":
    nums = [62, 65, 51, 15, 30, 63, 37, 8, 55, 70, 13, 84, 46, 44, 86, 11, 91, 10, 47, 3, 96, 9, 36, 54, 24, 55, 72,
            29, 45]
    selection_sort(nums)
    print(nums)