Insertion Sort 插入排序

核心结论

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

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

相关概念

• Sort Algorithms 排序算法
• Merge Sort 归并排序
• Quick Sort 快速排序
• Heap Sort 堆排序

1. 问题定义

给定一个长度为 $n$ 的序列：

$$A = \langle a_0,a_1,\ldots,a_{n-1}\rangle,$$

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

$$A' = \langle a'_0,a'_1,\ldots,a'_{n-1}\rangle,$$

满足：

$$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 时间复杂度

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

总移动次数为：

$$\sum_{i=1}^{n-1} i = \frac{n(n-1)}{2} = \Theta(n^2).$$

7.2 逆序对视角

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

$$T(n)=\Theta(n+I).$$

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

自适应性的来源

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

7.3 空间复杂度

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

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

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

8. 需要问题具有的性质

8.1 正确应用所需条件

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

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

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

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

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

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

不利场景

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

9. 算法性质

稳定性细节

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

10. 典型例子

对数组：

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

执行升序插入排序。

第 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(n)$ 个元素，因此整体最坏时间复杂度仍然是：

$$\Theta(n^2).$$

12.3 链表上的插入排序

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

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

14. 复习检查

• 能说明“已排序前缀”的含义
• 能使用 0-based 下标写出伪代码
• 能解释为什么内层循环使用 > 而不是 >=
• 能用循环不变式证明算法正确
• 能推导最坏情况下的 $\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.