插入排序

插入排序就是大多数人整理手中扑克牌的方法:拿起下一张牌,把它插到已排好的牌中的正确位置。它在很长的随机列表上很慢,但在短列表或基本有序的列表上非常快,所以实际的排序库至今仍在使用它。

正在排序的柱子:左边是已排序部分,一根柱子越过较大的柱子向前移入其中
正在排序的柱子:左边是已排序部分,一根柱子越过较大的柱子向前移入其中

基本思路

保持列表前端有序。开始时,已排序部分只有第一个值。取出下一个值,与它前面的值比较。如果前面的值更大,就交换,再向前一位继续比较。当前面的值不比它大,或它到达最前面时停下。已排序部分增加了一个值。对之后的每个值重复这一过程,直到末尾。

示例

以 5, 1, 4, 2, 8 为例。第 1 趟取出 1:5 更大,交换,1 到达最前面:1, 5, 4, 2, 8。第 2 趟取出 4:与 5 交换,然后停在 1 处:1, 4, 5, 2, 8。第 3 趟取出 2:与 5 和 4 交换,然后停在 1 处:1, 2, 4, 5, 8。第 4 趟取出 8,它已经比 5 大,一次比较就够了。共 7 次比较、4 次交换。同一列表上,冒泡排序需要 9 次比较,选择排序需要 10 次。

交换次数等于逆序对数

逆序对是顺序错误的一对值。交换两个顺序颠倒的相邻值,恰好消除一个逆序对,而插入排序只交换这样的相邻值。所以它的交换次数恰好等于初始列表的逆序对数,与冒泡排序相同。每一趟还最多有一次不导致交换的比较,也就是让它停下的那次。所以比较次数等于逆序对数加上最多 n − 1。

自适应:列表基本有序时很快

因为工作量等于逆序对数加上约 n,所以逆序对少时插入排序就很快。已排序的列表需要 n − 1 次比较、零次交换。如果每个值离正确位置只有几位,所需时间接近 n。只有远未排好的列表,比如有 n(n − 1)/2 个逆序对的倒序列表,所需时间才与 n² 成正比。随机列表平均约需 n²/4 次交换。

应用场景

插入排序是稳定的,不需要额外内存,开销也很小。对于短列表,它比理论上更快的算法还要快。许多库的排序算法,比如 Python 和 Java 中的 Timsort,以及 C++ 中使用的 introsort,都会在处理列表的小片段时改用插入排序,通常最多几十个值。它也适合逐个到达的数据,因为每个新值一到就能插入。

动手试试

打开应用,按“播放”,或按“单步”逐次比较。正在插入的值有自己的颜色,与它比较的值会高亮显示,已排序部分为绿色。与冒泡排序和选择排序不同,绿色部分并不是最终结果:后面更小的值仍可能插进来。先试试基本有序的列表,看看每一趟有多短,再试试倒序的列表。

常见问题

插入排序的时间复杂度是多少?

最坏和平均情况为 O(n²),最好情况(列表已排序)为 O(n)。更准确地说,所需时间与 n 加上逆序对数成正比。它只需要 O(1) 的额外内存。

插入排序和选择排序有什么区别?

选择排序要扫描整个未排序部分来找最小值,所以总是进行 n(n − 1)/2 次比较,但交换很少。插入排序按顺序取出下一个值,只把它向前移动必要的距离,所以比较更少(在基本有序的列表上尤其如此),但交换更多。

什么是二分插入排序?

这是一种变体,它在已排序部分中用二分查找确定新值的位置,只需约 log n 次比较,而不是最多 n 次。但为了腾出位置,仍需移动这些值,所以移动次数和 O(n²) 的最坏情况都不变。

插入排序稳定吗?

稳定。一个值只会向前越过严格更大的值,所以相等的值保持原来的顺序。

准备好尝试了吗?

在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。

试试插入排序