基本思路
把列表分成左边的已排序部分(起初为空)和右边的未排序部分。扫描未排序部分,记住最小值的位置。把这个值与第一个未排序的值交换:已排序部分增加一个。重复这一过程,直到只剩一个值,它必然是最大的。
示例
以 5, 1, 4, 2, 8 为例。第一趟扫描全部五个值,找到最小的 1,并与 5 交换:1, 5, 4, 2, 8。第二趟扫描 5, 4, 2, 8,找到 2 并与 5 交换:1, 2, 4, 5, 8。第三趟发现 4 已就位,第四趟发现 5 已就位,都不需要移动。总共 4 + 3 + 2 + 1 = 10 次比较,只有 2 次交换。同一个列表,冒泡排序需要 4 次交换。
比较次数总是相同
要确定哪个值最小,扫描必须查看剩下的每一个值。第 1 趟进行 n − 1 次比较,第 2 趟 n − 2 次,依此类推直到 1 次,总计 n(n − 1)/2 次。这个数字与列表无关:有序列表的比较次数和倒序列表完全一样。选择排序无法提前结束,因为即使扫描发现最小值已在最前面,也无从得知其余部分的情况。
交换很少
每一趟最多交换一次,所以选择排序的交换次数从不超过 n − 1 次,而且最小值已就位时会跳过交换。冒泡排序和插入排序的交换次数等于逆序对的数量,可能达到约 n²/2。当写入一个值的代价远高于读取两个值时,例如在每次写入都会造成损耗的存储器上,交换少就是优势。
不稳定
如果相等的值保持原来的顺序,这种排序就是稳定的。选择排序不稳定,因为一次远距离的交换可能让某个值越过与它相等的值。在 2, 2, 1 中,第一趟把第一个 2 与 1 交换,得到 1, 2, 2,两个 2 的顺序颠倒了。把中间的值依次移位而不是交换的版本是稳定的,但要移动多得多的值。
动手试试
打开应用并按“播放”,或按“单步”逐次比较。正在扫描的值会高亮显示,当前最小值有自己的颜色,每一趟都以一次交换结束,把它放进左边的已排序部分。试试有序列表和倒序列表:比较次数相同,只有交换次数不同。
常见问题
选择排序的时间复杂度是多少?
任何情况下都是 O(n²):对 n 个值,无论顺序如何,都恰好进行 n(n − 1)/2 次比较。它最多交换 n − 1 次,只需 O(1) 的额外内存。
选择排序和冒泡排序有什么区别?
冒泡排序边比较边交换相邻的值,一旦某一趟没有交换就能提前结束。选择排序只记住最小值的位置,每趟结束时交换一次。选择排序的交换更少;冒泡排序在基本有序的列表上更快。
选择排序稳定吗?
不稳定。一次交换可能让某个值越过与它相等的另一个值,因此相等的值可能改变顺序。用移位代替交换可以使它稳定,但需要更多的移动。
堆排序和选择排序有什么关系?
堆排序是一种找下一个值更快的选择排序:它把未排序部分保存在堆中,因此每次选择只需大约 log n 步,而不必完整扫描。这样总时间就降到 O(n log n)。
准备好尝试了吗?
在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。
试试选择排序