选择排序

选择排序是最简单朴素的排序算法，但是时间复杂度较高，且不是稳定排序。其他基础排序算法都是基于选择排序的优化。

• 练习题目: 力扣第 912 题 数组排序，先不纠结时间复杂度

想法

现在就是给你输入一个数组，让你写个排序算法把所有元素从小到大排序，你来说，怎么写？

我第一次思考这个问题时，想到的最直接的方法是这样的：

先遍历一遍数组，找到数组中的最小值，然后把它和数组的第一个元素交换位置；接着再遍历一遍数组，找到第二小的元素，和数组的第二个元素交换位置；以此类推，直到整个数组有序。

这个算法有一个被大家熟知的名字，叫做「选择排序」，即每次都去遍历选择最小的元素。

算法步骤

1. 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
2. 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
3. 重复第二步，直到所有元素均排序完毕。

代码实现

def sort(nums: List[int]) -> None:
    n = len(nums)
    # sortedIndex 是一个分割线
    # 索引 < sortedIndex 的元素都是已排序的
    # 索引 >= sortedIndex 的元素都是未排序的
    # 初始化为 0，表示整个数组都是未排序的
    sortedIndex = 0
    while sortedIndex < n:
        # 找到未排序部分 [sortedIndex, n) 中的最小值
        minIndex = sortedIndex
        for i in range(sortedIndex + 1, n):
            if nums[i] < nums[minIndex]:
                minIndex = i
        # 交换最小值和 sortedIndex 处的元素
        nums[sortedIndex], nums[minIndex] = nums[minIndex], nums[sortedIndex]

        # sortedIndex 后移一位
        sortedIndex += 1

时间复杂度

选择排序的最好时间复杂度是 $O(n^2)$，最坏时间复杂度是 $O(n^2)$，平均时间复杂度是 $O(n^2)$。

空间复杂度

选择排序的空间复杂度是$O(1)$，因为只需要一个辅助变量来记录最小（大）元素的索引。

稳定性

选择排序不是稳定排序算法。