3.2 插入排序与循环不变式
这一节，你能解决什么问题
学完这一节，你能够：
- 判断一个排序算法是否正确，不是靠"跑一遍看看"，而是用循环不变式证明
- 估算排序算法在不同情况下的代价，知道什么时候 Θ(n²) 是可接受的
- 审查 agent 给出的排序代码，发现边界条件错误和隐藏性能问题
问题情境
你正在整理一叠扑克牌。
牌已经拿在手里了，你需要把它们按从小到大排序。你会怎么做？
大多数人会这样：
拿起一张牌，插入到已整理好的牌堆中的正确位置。
这很自然。但问题是：为什么这个方法是对的？能不能更快？
让我们先把直觉变成算法，然后回答这两个问题。
直观思路
整理扑克牌的过程可以分解成几个步骤：
- 第一张牌：只有一个元素，天然有序
- 第二张牌：和第一张比，该在前就在前，该在后就在后
- 第三张牌：和前面两张比，找到正确位置插入
- ...以此类推
关键思想：每次只处理一张新牌，把它插入到已整理部分。
这样的好处是什么？
- 不需要知道后面还有多少牌
- 可以随时停下来，前面部分始终有序
- 如果牌几乎已经有序，只需很少的比较
问题：这个思路怎么变成代码？
规范定义
先定义问题：
输入：数组 A[0..n-1]，包含 n 个元素 输出：数组 A[0..n-1]，元素从小到大排列 约束：原地排序，只使用 O(1) 额外空间
插入排序的定义：
对于每个位置 i（从 1 到 n-1）：
- 把 A[i] 插入到 A[0..i-1] 的正确位置
- 插入后，A[0..i] 有序
为什么这样定义？
因为我们要保证一个不变量：在任何时刻，已处理部分始终有序。
这个不变量有三个好处：
- 每次只需考虑一个新元素
- 任何时候停下来，前面部分都可以使用
- 可以用于"增量排序"——数据逐步到达时
算法实现
def insertion_sort(A):
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 # 插入到正确位置一步步执行：
初始：[5, 2, 4, 6, 1, 3]
i=1: key=2, 找位置
[5, 2] → 5 > 2, 后移 → [|2, 5] → 2 插入位置0
结果：[2, 5, 4, 6, 1, 3]
i=2: key=4, 找位置
[2, 5] 中，5 > 4, 后移 → [2, |4, 5]
结果：[2, 4, 5, 6, 1, 3]
i=3: key=6, 找位置
[2, 4, 5] 中，都 < 6, 不移动
结果：[2, 4, 5, 6, 1, 3]
i=4: key=1, 找位置
[2, 4, 5, 6] 都 > 1, 全部后移
结果：[1, 2, 4, 5, 6, 3]
i=5: key=3, 扻位置
[1, 2, 4, 5, 6] 中，4,5,6 > 3, 后移
结果：[1, 2, 3, 4, 5, 6]这个方法是怎么想到的
你可能会问：为什么用"插入"而不是"交换"？
让我们看看另一种思路：
思路A（选择排序）：每次找最小的，放到前面
- 找最小值需要扫描整个数组
- 每次只能确定一个位置
- 即使数据已经有序，还是要全部扫描
思路B（插入排序）：每次把新元素插入正确位置
- 只需要和前面已有序部分比较
- 如果数据已经有序，每个元素只需一次比较
对比：
| 场景 | 选择排序 | 插入排序 |
|---|---|---|
| 已有序数据 | Θ(n²)（还是要全部扫描） | Θ(n)（每次只比一次） |
| 逆序数据 | Θ(n²) | Θ(n²) |
| 随机数据 | Θ(n²) | Θ(n²) |
洞察：插入排序的优势在于"增量维护有序"——如果数据已经接近有序，插入排序只需要很少的工作。
正确性分析
现在回答第一个问题：为什么这个方法是对的？
用循环不变式证明。
什么是循环不变式？
循环不变式是数学归纳法在程序上的应用：
- 初始化：循环开始前，不变式成立
- 保持：每次迭代后，不变式仍然成立
- 终止：循环结束时，不变式给出我们想要的结论
插入排序的循环不变式
不变式：在 for 循环的每次迭代开始时，子数组 A[0..i-1] 包含原来在 A[0..i-1] 的元素，且已排序。
证明：
1. 初始化
i = 1 时，A[0..0] 只有一个元素。单个元素天然有序。不变式成立。
2. 保持
假设迭代开始时 A[0..i-1] 已排序。
算法把 A[i] 插入到 A[0..i-1] 中：
- while 循环把所有 > key 的元素后移
- 最后把 key 放到空出的位置
插入后，A[0..i] 有序，且包含原来 A[0..i] 的所有元素。
迭代结束后，i 增加到 i+1。新的迭代开始时，A[0..(i+1)-1] = A[0..i] 已排序。不变式保持。
3. 终止
循环结束条件：i = n。
此时 A[0..n-1] 已排序。这就是整个数组。
结论：插入排序正确。
复杂度分析
现在回答第二个问题：代价是什么？
时间复杂度
关键量：比较次数和移动次数。
让我们分析三种情况：
情况一：已有序
[1, 2, 3, 4, 5]每个元素只需和前一个比一次，发现已经有序。
- 比较次数：n-1
- 移动次数：0
- 复杂度：Θ(n)
情况二：逆序
[5, 4, 3, 2, 1]每个元素都要和前面所有元素比，并且全部移动。
i=1: key=4, 比较1次, 移动1次
i=2: key=3, 比较2次, 移动2次
i=3: key=2, 比较3次, 移动3次
i=4: key=1, 比较4次, 移动4次
总比较：1+2+3+4 = (n-1)n/2
总移动：1+2+3+4 = (n-1)n/2复杂度：Θ(n²)
情况三：随机
一个关键概念：倒置数。
倒置是数组中逆序的一对元素：i < j 但 A[i] > A[j]。
- 已有序：0 个倒置
- 逆序：n(n-1)/2 个倒置
- 随机排列：期望倒置数 = n(n-1)/4
为什么是 n(n-1)/4？
n(n-1)/2 对元素，每对有 1/2 概率是倒置。期望 = 总数 × 概率。
插入排序每次比较和移动消除一个倒置。
期望比较次数 ≈ 期望倒置数 = Θ(n²/4)
复杂度：Θ(n²)
空间复杂度
原地排序，只用了几个变量（key, i, j）。
空间复杂度：Θ(1)
什么时候不该用这个方法
插入排序不是万能的。什么时候该用，什么时候不该用？
该用的情况
小规模数据（n < 50）
- Θ(n²) 和 Θ(n log n) 差别很小
- 插入排序实现简单，常数小
几乎有序的数据
- 倒置数很少时，接近 Θ(n)
- 比如：已排序数组中插入少量新元素
数据逐步到达
- 可以增量维护有序
- 不需要等所有数据到达再排序
作为其他排序的子过程
- 快排、归并在小数组时切换到插入排序
- 实际库函数中的常见优化
不该用的情况
大规模随机数据
- Θ(n²) 太慢
- 应该用 Θ(n log n) 的算法
逆序或接近逆序的数据
- Θ(n²) 最坏情况
- 如果数据分布未知，不应该依赖插入排序
需要稳定性的场景，但数据量大
- 插入排序是稳定的，但太慢
- 应该用归并排序（稳定且 Θ(n log n））
本节小结
解决了什么问题？
- 原地排序数组，使用简单的"插入"思想
- 用循环不变式证明算法正确，不靠"跑一遍看看"
- 分析了不同情况下的代价
核心方法是什么？
- 增量有序：每次只处理一个新元素，维护已有序部分
- 循环不变式：数学归纳法用于程序证明
为什么正确？
循环不变式保证：
- 开始时：单元素有序
- 每次迭代：保持有序
- 结束时：整个数组有序
代价是什么？
- 最好：Θ(n)（已有序）
- 最坏：Θ(n²)（逆序）
- 平均：Θ(n²)
- 空间：Θ(1)
适用场景？
小规模、几乎有序、增量到达。不适合大规模随机数据。
能否自己使用？
能。关键是记住：
- 不要盲目用于大数据
- 用循环不变式验证代码（包括 agent 写的）
- 倒置数决定代价
练习
基本理解
练习 1：对数组 [3, 1, 4, 1, 5, 9, 2, 6]，画出插入排序每一步的状态。
练习 2：计算数组 [3, 1, 4, 1, 5, 9, 2, 6] 的倒置数。
练习 3：为什么插入排序是稳定的？稳定性在什么场景重要？
方法应用
练习 4：写出插入排序内循环的循环不变式，并证明：
while 循环开始时，A[j+1..i] 的元素都大于 key，且保持原来顺序。
练习 5：设计一个"在线排序"场景：数据逐步到达，每收到一个新数据就维护有序。写出伪代码。
错误诊断
练习 6：以下代码有什么问题？
def insertion_sort_bug(arr):
for i in range(len(arr)): # ← 这里
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key提示：用循环不变式验证 i=0 时的情况。
练习 7：为什么 A[j + 1] = key 而不是 A[j] = key？写出边界条件分析。
方案比较
练习 8：比较插入排序和选择排序：
| 维度 | 插入排序 | 选择排序 |
|---|---|---|
| 最好复杂度 | ||
| 最坏复杂度 | ||
| 空间复杂度 | ||
| 是否稳定 | ||
| 适用场景 |
填完表格后，给出一个选择建议：什么时候用插入，什么时候用选择？
开放设计
练习 9：二分插入排序。
用二分查找找插入位置，减少比较次数。写出算法并分析：
- 比较次数减少了吗？
- 移动次数减少了吗？
- 时间复杂度改变了吗？
练习 10：审查 agent 输出。
让 agent 写一个插入排序实现，然后用循环不变式审查：
- 循环范围是否正确？
- 内循环条件是否正确？
- 插入位置是否正确？
- 边界情况（空数组、单元素、全相等）是否处理？
写一份审查报告。
上一节：3.1 理论极限
下一节：3.3 分治排序