← Back

Insertion Sort 插入排序

Insertion Sort 插入排序

核心结论

插入排序从左向右维护一个已经排好序的前缀，每次取出下一个元素，将它插入前缀中的正确位置。

  • 最好时间复杂度：Θ(n)\Theta(n)
  • 平均、最坏时间复杂度：Θ(n2)\Theta(n^2)
  • 额外空间复杂度：Θ(1)\Theta(1)
  • 特性：原地、稳定、自适应、在线
  • 适用场景：规模较小或接近有序的数据

相关概念

1. 问题定义

给定一个长度为 nn 的序列：

A=⟨a0,a1,…,an−1⟩,A = \langle a_0,a_1,\ldots,a_{n-1}\rangle,

要求输出该序列的一个排列：

A′=⟨a0′,a1′,…,an−1′⟩,A' = \langle a'_0,a'_1,\ldots,a'_{n-1}\rangle,

满足：

a0′≤a1′≤⋯≤an−1′.a'_0 \le a'_1 \le \cdots \le a'_{n-1}.

本文默认按非递减顺序排序，并统一使用 0-based 下标。

2. 基本思想

插入排序类似于整理手中的扑克牌：

  1. 将第一个元素视为已经有序；
  2. 从左到右依次取出一个待排序元素 key；
  3. 在它左侧的有序区间中从右向左查找插入位置；
  4. 将所有大于 key 的元素向右移动一位；
  5. 将 key 放入空出的位置。

在处理下标 i 之前，数组具有如下结构：

A[0 : i]       A[i]       A[i + 1 : n]
已排序前缀      key         尚未处理

处理完成后，已排序前缀由 A[0:i] 扩展为 A[0:i+1]。

核心操作

插入排序不是不断交换相邻元素，而是先保存 key，再将较大的元素整体向右移动，最后写入 key。这种写法通常比连续交换减少赋值操作。

3. 具体过程

设当前处理元素为 A[i]：

  1. 保存当前元素：key = A[i]；
  2. 令 j = i - 1，从已排序前缀的末尾开始检查；
  3. 当 j >= 0 且 A[j] > key 时：
    • 将 A[j] 移到 A[j + 1]；
    • 令 j = j - 1；
  4. 循环结束时，j + 1 就是 key 的插入位置；
  5. 执行 A[j + 1] = key。

区间变化

第 i 轮开始前，A[0:i] 已经有序；第 i 轮结束后，A[0:i+1] 已经有序，并且包含原来该区间中的全部元素。

4. 循环不变式与正确性

循环不变式

在外层循环每次迭代开始时，子数组 A[0:i] 已按非递减顺序排列，并且包含原始数组前 i 个元素的一个排列。

4.1 初始化

第一次迭代时 i = 1，前缀 A[0:1] 只包含一个元素。单元素序列天然有序，因此循环不变式成立。

4.2 保持

假设第 i 轮开始时 A[0:i] 已经有序。算法将 A[i] 保存为 key，把前缀中所有大于 key 的元素向右移动，随后将 key 放入正确位置。因此新前缀 A[0:i+1] 有序，且元素集合没有改变。

4.3 终止

外层循环终止时 i = n。根据循环不变式，整个数组 A[0:n] 已经有序，并且是原数组元素的一个排列，因此插入排序正确。

5. 伪代码

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

前置条件与后置条件

Precondition:
    A 是一个长度为 n 的可修改序列；
    A 中任意两个关键字可以按一致的顺序进行比较。

Postcondition:
    A[0] <= A[1] <= ... <= A[n - 1]；
    排序后的 A 是原 A 的一个排列。

6. Python 实现

def insertion_sort(a: list[int]) -> None:
    """使用插入排序原地按非递减顺序排列列表。"""
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1

        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]
            j -= 1

        a[j + 1] = key


if __name__ == "__main__":
    data = [8, 2, 4, 9, 3, 6]
    insertion_sort(data)
    print(data)

    assert data == [2, 3, 4, 6, 8, 9]

预期输出：

[2, 3, 4, 6, 8, 9]

7. 时空间复杂度

7.1 时间复杂度

设外层循环当前处理下标为 ii。在最坏情况下，key 需要与左侧的 ii 个元素比较并跨过它们。

总移动次数为：

∑i=1n−1i=n(n−1)2=Θ(n2).\sum_{i=1}^{n-1} i = \frac{n(n-1)}{2} = \Theta(n^2).
情况输入特征时间复杂度原因
最好情况已按非递减顺序排列Θ(n)\Theta(n)每轮只进行一次关键比较，不发生右移
平均情况元素次序近似随机Θ(n2)\Theta(n^2)每个元素平均跨过其左侧约一半元素
最坏情况严格递减排列Θ(n2)\Theta(n^2)每个 key 都要移动到当前前缀最左侧

7.2 逆序对视角

若数组中的逆序对数量为 II，则插入排序执行的元素右移次数恰好为 II。因此可以更精确地写成：

T(n)=Θ(n+I).T(n)=\Theta(n+I).
  • 已排序数组：I=0I=0，因此 T(n)=Θ(n)T(n)=\Theta(n)；
  • 逆序数组：I=n(n−1)2I=\frac{n(n-1)}{2}，因此 T(n)=Θ(n2)T(n)=\Theta(n^2)。

自适应性的来源

插入排序的运行时间会随逆序对数量减少而降低，所以它对“接近有序”的输入尤其有效。

7.3 空间复杂度

算法只使用 key、i、j 等常数个额外变量：

S(n)=Θ(1).S(n)=\Theta(1).

因此插入排序属于原地排序。

8. 需要问题具有的性质

8.1 正确应用所需条件

  1. 元素必须可比较
    比较规则应具有一致性，能够定义一个总顺序或总预序，不能出现比较结果彼此矛盾的情况。

  2. 序列必须允许访问和修改前面的元素
    标准数组版本需要读取 A[j] 并将元素向右移动，因此适合数组、列表等可修改序列。

  3. 目标是按关键字建立线性顺序
    例如数值大小、字符串字典序，或对象的某个可比较字段。

  4. 相等元素不要求互不相同
    插入排序允许重复元素；使用条件 A[j] > key 时，相等元素的相对次序不变。

8.2 更适合插入排序的输入特征

  • 输入规模较小；
  • 数据已经基本有序；
  • 逆序对数量较少；
  • 数据逐个到达，需要随到随排；
  • 希望使用稳定且额外空间为常数的排序方法；
  • 作为归并排序、快速排序等算法处理小规模子数组时的基础排序器。

不利场景

对规模较大且高度无序的数组，Θ(n2)\Theta(n^2) 的移动成本通常过高，应优先考虑 归并排序、堆排序 或经过工程优化的 快速排序。

9. 算法性质

性质结论说明
比较排序是排序依据是元素之间的比较
原地排序是额外空间为 Θ(1)\Theta(1)
稳定排序是内层条件使用 A[j] > key，不会越过相等元素
自适应排序是运行时间与逆序对数量有关
在线算法是新元素到达后可插入已经排好序的前缀
是否需要递归否标准实现完全迭代

稳定性细节

若把内层条件改成 A[j] >= key，后出现的相等元素可能被插到先出现元素之前，从而破坏稳定性。

10. 典型例子

对数组：

[8, 2, 4, 9, 3, 6]

执行升序插入排序。

轮次ikey本轮操作本轮结束后的数组
初始——A[0:1] 视为有序[8, 2, 4, 9, 3, 6]
1128 右移，2 插入下标 0[2, 8, 4, 9, 3, 6]
2248 右移，4 插入下标 1[2, 4, 8, 9, 3, 6]
3399 已在正确位置[2, 4, 8, 9, 3, 6]
4439、8、4 右移，3 插入下标 1[2, 3, 4, 8, 9, 6]
5569、8 右移，6 插入下标 3[2, 3, 4, 6, 8, 9]

第 4 轮的详细过程

当前状态：

[2, 4, 8, 9, 3, 6]
             ^
           key = 3

依次移动：

9 > 3  -> [2, 4, 8, 9, 9, 6]
8 > 3  -> [2, 4, 8, 8, 9, 6]
4 > 3  -> [2, 4, 4, 8, 9, 6]
2 <= 3 -> 停止移动

将 key 写入下标 1：

[2, 3, 4, 8, 9, 6]

11. 常见错误

边界条件写错

内层循环必须先判断 j >= 0，再访问 A[j]。

忘记保存

key 元素右移会覆盖原来的 A[i]，因此必须在移动前执行 key = A[i]。

忘记最终写回

内层循环只负责腾出位置，结束后仍需执行 A[j + 1] = key。

混淆已排序区间

使用 0-based 半开区间时，第 i 轮开始前的有序前缀是 A[0:i]，不包含 A[i]。

12. 常见变体

12.1 降序插入排序

将比较条件：

A[j] > key

改为：

A[j] < key

即可按非递增顺序排列。

12.2 二分插入排序

可以使用二分查找在有序前缀中寻找插入位置，将寻找位置所需的比较次数降为 O(log⁡n)O(\log n)。

但是插入前仍可能需要移动 O(n)O(n) 个元素，因此整体最坏时间复杂度仍然是：

Θ(n2).\Theta(n^2).

12.3 链表上的插入排序

链表插入节点本身可以是 O(1)O(1)，但寻找插入位置仍需要线性扫描，因此整体时间复杂度通常仍为 Θ(n2)\Theta(n^2)。

13. 与其他排序算法的简要比较

算法最好时间平均时间最坏时间额外空间稳定性
插入排序Θ(n)\Theta(n)Θ(n2)\Theta(n^2)Θ(n2)\Theta(n^2)Θ(1)\Theta(1)稳定
归并排序Θ(nlog⁡n)\Theta(n\log n)Θ(nlog⁡n)\Theta(n\log n)Θ(nlog⁡n)\Theta(n\log n)Θ(n)\Theta(n)稳定
堆排序Θ(nlog⁡n)\Theta(n\log n)Θ(nlog⁡n)\Theta(n\log n)Θ(nlog⁡n)\Theta(n\log n)Θ(1)\Theta(1)不稳定
快速排序Θ(nlog⁡n)\Theta(n\log n)Θ(nlog⁡n)\Theta(n\log n)Θ(n2)\Theta(n^2)与实现有关通常不稳定

14. 复习检查

  • 能说明“已排序前缀”的含义
  • 能使用 0-based 下标写出伪代码
  • 能解释为什么内层循环使用 > 而不是 >=
  • 能用循环不变式证明算法正确
  • 能推导最坏情况下的 Θ(n2)\Theta(n^2)
  • 能解释插入排序为什么对近乎有序的数组较快
  • 能说明右移次数与逆序对数量之间的关系

参考资料

  1. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford. Introduction to Algorithms, 3rd ed., MIT Press, 2009, Section 2.1: Insertion Sort.
  2. Demaine, Erik D.; Leiserson, Charles E. Introduction to Algorithms, Lecture 1: Analysis of Algorithms, MIT, 2006.