选择排序

参考: 选择排序(动图理解)

# selectsort
"""
认为第一个数是最小的，遍历后面的数跟一个数比，如果比第一个数，记录下来
遍历完毕后得出后面的数中最小的数，和第一个交换位置
此时第一个数已经是最小的，继续遍历，认为第2个数是剩余所有数中最小的，继续重复上述步骤即可
"""


def select_sort(li):
    n = len(li)
    # 内部循环每次找到一个最小的数，共需要n-1次
    for j in range(n - 1):  # j=1

        # 记录0位置，认为0位置就是最小的数
        min = j
        # 遍历后面的数据，与最小的数进行比较
        for i in range(j + 1, n):
            if li[i] < li[min]:
                min = i
        # 循环结束时，min指向的是最小的数，把最小的数放到剩下的无序序列的最前面
        li[min], li[j] = li[j], li[min]


if __name__ == '__main__':
    l = [4, 2, 3, 5, 1]
    l = [5, 4, 3, 2, 1]
    select_sort(l)
    print(l)
    # 稳定性：不稳定
    # 最坏时间复杂度：O(n^2)
    # 最优时间复杂度：O(n^2)