选择排序

(图片来自 选择排序 - 十大经典排序算法

思路

选择排序像另一种打扑克牌时候的排序方式(插入排序也是),比如说牌已经发好拿起来是乱序的,我们就每次从乱序的牌中选择一张最小的放到排好序的牌中,挑完一遍就好了。其算法步骤如下:

  1. 在待排序的数组中找到最小的元素,移动(或交换)到该数组的开头,作为已排序数组。
  2. 重复第 1 步,每次都将待排序数组中的最小元素移动(或交换)到已排序数组的末尾,直到完成排序。

分析

  • 平均、最好、最坏时间复杂度都为 $O(n^2)$,因为每次只选择一个数,而选择这个数需要比较剩下所有未排序数组,因此复杂度总为 $O(n^2)$。
  • 空间复杂度为 $O(1)$,不需要额外空间。
  • 如果在移动最小元素的时候是通过「替换」的话,算法不稳定;如果是通过「插入」的话,算法稳定

实现

见《🔢 排序算法 00. 代码实现》(本博客)。