插入排序是一种基于比较的排序算法,它逐个元素构建有序序列。每一步都从未排序部分取出下一个元素,将其插入已排序部分的正确位置。其标准数组实现简单、稳定,且仅需常数辅助空间。虽然平均和最坏情况下的运行时间均为二次量级,但对于小规模或已接近有序的输入,它的效率很高。
方法
插入排序维护输入序列的一个有序前缀。最初,该前缀仅包含第一个元素。对于后续每个称为待插入元素(key)的元素,算法执行以下操作:
- 将待插入元素保存在临时变量中。
- 从后向前遍历有序前缀,将待插入元素与前面的元素比较。
- 将大于待插入元素的元素向右移动一位。
- 将待插入元素放入移动后留下的空位。
这类似于整理手中的扑克牌:每拿到一张新牌,就将它插入已经排好序的牌中。
例如,对数组 排序时,每次插入后的状态如下:
初始状态: [5, 2, 4, 6, 1, 3]
插入 2: [2, 5, 4, 6, 1, 3]
插入 4: [2, 4, 5, 6, 1, 3]
插入 6: [2, 4, 5, 6, 1, 3]
插入 1: [1, 2, 4, 5, 6, 3]
插入 3: [1, 2, 3, 4, 5, 6]
插入 时不需要移动任何元素,因为它已经大于有序前缀中的所有元素。
伪代码与正确性
对于下标从零开始的数组,标准实现可用以下伪代码表示:
INSERTION-SORT(A):
n = length(A)
for i = 1 to n - 1:
key = A[i]
j = i - 1
while j >= 0 and A[j] > key:
A[j + 1] = A[j]
j = j - 1
A[j + 1] = key
while 条件中的逻辑与采用从左到右的短路求值,因此当 j 为负数时,不会访问 A[j]。
算法的正确性可由一个循环不变量证明:在外层循环的第 次迭代开始前,前缀 包含原始输入的前 个元素,且已按顺序排列。
- 初始化: 仅包含一个元素的前缀是有序的。
- 保持: 将较大的元素右移并插入待插入元素,既保留了前缀中的所有元素,又使有序前缀的长度增加一。
- 终止: 所有元素处理完毕后,有序前缀就是整个数组。
这一论证是形式验证中常用推理方法的典型示例。
复杂度与自适应性
标准实现的时间复杂度在很大程度上取决于输入顺序。假设比较和元素赋值操作均耗时常数:
| 输入情况 | 运行时间 |
|---|---|
| 已经有序 | |
| 不同元素的均匀随机排列 | 期望为 |
| 元素互不相同且按逆序排列 | |
| 含有 个逆序对的一般输入 |
其中, 为元素个数。辅助空间复杂度为 :除输入数组外,仅需存储待插入元素和固定数量的下标。因此,标准实现是一种原地算法。
与逆序对的关系
逆序对是指满足 且对应元素顺序颠倒的一对位置:
在基于移位的实现中,向右移动的总次数等于原始输入中的逆序对数量 。每次移位都会让前面一个较大的元素越过当前待插入元素,恰好消除一个这样的逆序对。计入处理每个待插入元素的开销后,可得
这使插入排序具有自适应性:它能够利用输入中已有的顺序。这里,“接近有序”若指输入中逆序对较少,而不只是许多元素已经位于最终位置,就尤其有意义。
由互不相同的元素构成的逆序数组包含
个逆序对,因此需要同样次数的移位。对于 个不同元素的均匀随机排列,每一对元素构成逆序对的概率均为 ,因此有
这些界限统计的是基本操作次数。如果比较或记录移动的代价较高,各类操作本身的成本也会影响实际性能。
稳定性与排序规则
当插入排序仅在元素严格大于待插入元素时才将其右移,它就是一种稳定排序算法。此时,键值相等的元素会保持原有的相对顺序。
例如,记录 和 若按此顺序出现,在按数值分量排序后仍会保持这一顺序。若将条件从 A[j] > key 改为 A[j] >= key,则可能颠倒键值相等的记录的顺序,破坏稳定性。
与其他基于比较的排序算法一样,比较规则必须定义一致的次序。按选定字段对记录排序时,比较器对相等关系和先后次序的处理必须符合预期结果。
变体
折半插入排序
折半插入排序使用二分查找,在有序前缀中寻找插入位置。其最坏情况下的键值比较次数为 ,而非二次量级。
不过,对于数组,插入一个元素仍需移动插入位置与该元素原位置之间的所有元素。因此,最坏情况下的总运行时间仍为 。当比较的代价远高于移动时,这一变体很有用。要保持稳定性,实现时应将新元素插入到现有等值元素之后。
相邻交换插入排序
除了保存待插入元素并移动其他元素外,也可以在当前元素与其前一个元素顺序颠倒时,反复交换两者。这种实现的渐近复杂度相同,但通常比基于移位的版本执行更多次元素赋值。只要不交换相等的元素,它仍然是稳定的。
链表插入排序
插入排序也可以用于链表。一旦确定插入位置,就可以通过重新连接节点完成插入,无需移动一整段元素。不过,寻找插入位置通常仍需线性查找,因此普通链表插入排序在最坏情况下的运行时间为二次量级。
其自适应性取决于查找的组织方式:如果每次插入都从表头开始查找,就不一定能像数组版本那样,在输入已有序时达到线性运行时间。
应用与局限
插入排序常用于较大型排序过程中的小规模子数组。它的循环简短,初始化开销低,因此在数据规模较小时,可能比更复杂的方法更快,即使后者具有更优的渐近界限。因此,快速排序和归并排序的混合实现可能会在子数组规模低于某个阈值时切换为插入排序,具体阈值取决于实现。
插入排序也适合在新元素不断到来时维护有序序列。每个新元素都可以插入现有的有序前缀,而不必重新对整个序列排序。不过,数组插入仍可能耗费线性时间,因此,当需要进行大量更新时,这种方法不能替代更合适的数据结构。
对于数组实现,连续的内存访问有利于利用 CPU 缓存,但实际性能取决于元素大小、比较成本、编译器行为和硬件。选择插入排序时,并不存在普遍适用的最佳规模阈值。
其主要局限在于,面对规模大且顺序高度混乱的输入时,需要执行二次量级的操作。二分查找虽能减少比较次数,却无法消除数组元素移动的成本。对于此类工作负载,归并排序等最坏运行时间为 的算法能提供更强的可扩展性保证。