数据结构与算法 / 系统课时
插入排序
插入排序
插入排序通过不断扩展数组左侧的有序区完成排序。本课将把“取出当前元素、右移更大元素、插入空位”落实为 Java 代码,并用循环不变式说明算法为什么始终正确。
学习目标
- 描述插入排序每一轮如何扩展有序前缀。
- 编写稳定、原地且可运行的插入排序实现。
- 使用循环不变式证明正确性并分析时间、空间复杂度。
算法思路与正确性
插入排序把数组划分为左侧有序区和右侧未处理区。第 i 轮开始时,区间 0..i-1 已经有序;算法暂存 array[i],将有序区中比它大的元素依次右移,再把它写入空出的正确位置。

循环不变式
在每次外层循环开始时,子数组 array[0..i-1] 已按非递减顺序排列,并且包含原数组前 i 个元素的同一多重集合。
- 初始化:非空输入的首元素本身有序。空数组不进入循环,已经满足输出要求。
- 保持:右移所有大于
key的元素后,把key放入空位,新的array[0..i]仍然有序,元素也没有增加或丢失。 - 终止:当
i == array.length时,有序前缀覆盖整个数组,因此数组整体有序。
判断条件必须使用 array[j] > key。若改成 array[j] >= key,相等元素也会被越过,算法将失去稳定性。
复杂度
| 情况 | 比较与移动特征 | 时间复杂度 |
|---|---|---|
| 已有序 | 每轮只比较一次,不发生右移 | |
| 逆序 | 第 i 轮右移 i 个元素 |
|
| 一般输入 | 每个逆序对对应一次右移 | ,I 为逆序对数(n≥1) |
排序核心只保存 key、i、j 等常数个变量。若启用逐轮打印,格式化整张表在每轮都会消耗线性时间和临时字符串空间,即使原输入已有序也会有平方级输出工作。它是原地、稳定、在线的比较排序,适合规模较小或接近有序的数据。
完整实现
将代码保存为 InsertionSortDemo.java。程序在每轮结束后输出数组状态,便于核对有序区是否按预期扩大。
import java.util.Arrays;
public class InsertionSortDemo {
public static void main(String[] args) {
int[] values = {7, 3, 5, 2, 9, 1};
System.out.println("原始数组: " + Arrays.toString(values));
insertionSort(values, true);
System.out.println("排序结果: " + Arrays.toString(values));
}
private static void insertionSort(int[] array, boolean trace) {
for (int i = 1; i < array.length; i++) {
int key = array[i];
int j = i - 1;
// 为 key 腾出位置,只右移严格大于 key 的元素。
while (j >= 0 && array[j] > key) {
array[j + 1] = array[j];
j--;
}
array[j + 1] = key;
if (trace) {
System.out.println("第 " + i + " 轮: " + Arrays.toString(array));
}
}
}
}编译并运行:
javac -encoding UTF-8 InsertionSortDemo.java
java InsertionSortDemo预期输出
原始数组: [7, 3, 5, 2, 9, 1]
第 1 轮: [3, 7, 5, 2, 9, 1]
第 2 轮: [3, 5, 7, 2, 9, 1]
第 3 轮: [2, 3, 5, 7, 9, 1]
第 4 轮: [2, 3, 5, 7, 9, 1]
第 5 轮: [1, 2, 3, 5, 7, 9]
排序结果: [1, 2, 3, 5, 7, 9]边界、错误与练习
空数组和单元素数组不会进入外层循环,因此无需单独分支。常见错误是把 key 直接留在数组中而不先保存,右移时会覆盖待插入值;另一个错误是在循环结束后写成 array[j] = key,当 j == -1 时会越界,正确位置始终是 j + 1。
练习一:把示例改为降序排序。保持算法稳定,并让每轮输出仍能体现左侧有序区。验收条件是输入 [3, 1, 3, 2] 后得到 [3, 3, 2, 1],给两个键为 3 的记录分别标记 A 和 B,额外验证 A 仍在 B 前。只用整数数组无法区分相同值的记录身份。
练习二:在不改变排序结果的前提下统计比较次数和右移次数,分别测试已有序、逆序和随机数组。验收条件是已有序数组的右移次数为 0,长度为 n、关键字严格降序时,右移次数为 n(n−1)/2。含相等值时,逆序对只计严格大于。
本课总结
- 插入排序通过把当前元素插入有序前缀来逐步扩大已排序区。
- 循环不变式同时保证前缀有序和元素集合不变,从而证明最终结果正确。
- 严格大于判断保证稳定性;算法辅助空间为 ,最坏时间为 。
下一课预告
下一阶段将继续比较其他基于关键字比较的排序方法,重点观察它们在移动次数、稳定性和最坏时间复杂度上的不同取舍。