GESP C++ 四级：插入排序精讲

核心目标：理解插入排序的核心思想与执行流程，掌握标准代码实现，理解时间复杂度、空间复杂度和稳定性，能熟练判断排序过程、分析复杂度，并解决综合应用问题。
插入排序像“打扑克摸牌”——把新摸到的牌插入到左手已经排好序的牌中；每一轮将当前元素插入到前面已排序序列的合适位置。最好 O(n)，最坏/平均 O(n²)，空间 O(1)，是稳定排序。

一、考纲定位

根据 CCF 官方考纲，四级知识内容明确包含：

• 排序概念和稳定性
• 经典排序（冒泡排序、插入排序、选择排序等）
• 简单算法复杂度的估算

插入排序与冒泡排序、选择排序并列为四级必须掌握的三大基础排序。考试中常见考法：

二、核心思想

插入排序的基本思想：

把数组分为“已排序”和“未排序”两部分。初始时，第一个元素视为已排序。然后依次将未排序部分的第一个元素插入到已排序部分的正确位置，直到全部元素有序。

形象理解：就像打扑克牌时，左手拿的是已经排好序的牌，右手每摸一张新牌，就把它插入到左手中合适的位置。

关键动作：从后往前扫描已排序部分，找到插入位置，同时把比当前元素大的元素依次后移。

三、执行流程图解

以数组 [5, 3, 8, 1] 升序排列为例：

初始状态：[5 | 3, 8, 1]，竖线左边是已排序部分。

第 1 轮：将 3 插入到已排序部分 [5] 中。

• 5 > 3，5 后移一位
• 将 3 放到空出的位置
• 结果：[3, 5 | 8, 1]

第 2 轮：将 8 插入到已排序部分 [3, 5] 中。

• 5 < 8，位置正确，不需要移动
• 结果：[3, 5, 8 | 1]

第 3 轮：将 1 插入到已排序部分 [3, 5, 8] 中。

• 8 > 1，8 后移
• 5 > 1，5 后移
• 3 > 1，3 后移
• 将 1 放到最前面
• 结果：[1, 3, 5, 8]

排序完成。

四、标准代码实现

4.1 移动法（推荐，标准写法）

for (int i = 1; i < n; i++) {
    int key = arr[i];       // 当前要插入的元素
    int j = i - 1;          // 从已排序部分的最后一个元素开始
    while (j >= 0 && arr[j] > key) {
        arr[j + 1] = arr[j]; // 比 key 大的元素后移
        j--;
    }
    arr[j + 1] = key;        // 将 key 插入到正确位置
}

代码要点：

• 外层循环 i 从 1 开始，因为第一个元素默认已排序。
• key 保存当前要插入的元素，避免被覆盖。
• 内层 while 从后往前扫描，把比 key 大的元素依次后移。
• j + 1 就是 key 最终要放置的位置。
• 升序用 arr[j] > key，降序改为 arr[j] < key。

4.2 交换法（另一种写法）

for (int i = 1; i < n; i++) {
    for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
        swap(arr[j], arr[j - 1]);
    }
}

这种写法类似冒泡，但方向是从后往前，每发现逆序就交换。两种写法效果相同，移动法效率略高。

五、时间复杂度与空间复杂度

重要结论：

• 插入排序在数据基本有序时效率极高，接近 O(n)。
• 插入排序的移动次数等于数组中逆序对的数量。这个性质在统计逆序对类题目中很有用。
• 与冒泡排序相比，插入排序在部分有序时优势明显；与选择排序相比，插入排序是稳定的，且最好情况更快。

六、稳定性分析

插入排序是稳定的排序算法。

原因：当 arr[j] == key 时，while 条件 arr[j] > key 不成立，不会将相等的元素后移，因此相等元素的相对顺序保持不变。

真题示例：

以下排序算法中，稳定的是（ ）。
A) 选择排序 B) 插入排序 C) 快速排序 D) 堆排序
答案：B

七、与冒泡、选择排序对比

八、真题精讲与应用

真题1：排序过程模拟（选择题）

对数组 [6, 2, 9, 4] 进行插入排序（升序），第 2 轮插入后的结果是（ ）。
A) [2, 6, 9, 4] B) [2, 4, 6, 9] C) [6, 2, 9, 4] D) [2, 6, 4, 9]
答案：A
解析：第 1 轮将 2 插入到 6 前面，得到 [2, 6, 9, 4]；第 2 轮将 9 插入，9 比 6 大，位置不变，仍为 [2, 6, 9, 4]。

真题2：代码填空

下面插入排序的代码中，横线处应填入（ ）。

for (int i = 1; i < n; i++) {
 int key = arr[i];
 int j = i - 1;
 while (j >= 0 && ______) {
     arr[j + 1] = arr[j];
     j--;
 }
 arr[j + 1] = key;
}

A) arr[j] > key B) arr[j] < key C) arr[j] >= key D) arr[j] <= key
答案：A
解析：升序插入，当已排序元素大于 key 时后移。

真题3：综合应用——统计逆序对

插入排序的移动次数恰好等于数组中逆序对的数量。因此可以用插入排序来统计逆序对。

题目：给定一个数组，统计其中逆序对的数量（即 i < j 但 a[i] > a[j] 的数对个数）。

int cnt = 0;
for (int i = 1; i < n; i++) {
    int key = arr[i];
    int j = i - 1;
    while (j >= 0 && arr[j] > key) {
        arr[j + 1] = arr[j];
        j--;
        cnt++;   // 每移动一次，说明有一个逆序对
    }
    arr[j + 1] = key;
}
cout << cnt << endl;

注意：这种方法统计逆序对的时间复杂度是 O(n²)，适合 n 较小的情况。数据量大时需用归并排序或树状数组（四级不要求）。

九、易错点汇总

1. 外层循环从 0 开始：插入排序第一个元素默认已排序，外层应从 i = 1 开始。
2. key 没有保存：直接使用 arr[i] 会在移动过程中被覆盖，必须用临时变量 key 保存。
3. 内层 while 条件顺序：j >= 0 && arr[j] > key 不能交换顺序，否则可能越界访问 arr[-1]。
4. 插入位置错误：循环结束后，key 应放在 arr[j + 1]，不是 arr[j]。
5. 升序降序条件写反：升序用 arr[j] > key，降序用 arr[j] < key。
6. 稳定性误解：插入排序是稳定的，但若写成 arr[j] >= key 就会变成不稳定。
7. 最好情况误判：插入排序最好情况是 O(n)，不是 O(n²)，这是与选择排序的重要区别。
8. 移动次数与交换次数混淆：插入排序的“移动”是赋值操作，不是 swap，但效果类似。

十、速查表

十一、总结

插入排序是 GESP 四级排序模块的三大基础排序之一。

1. 插入排序像打扑克摸牌，把新牌插入到已排好序的牌中。
2. 外层从 i = 1 开始，第一个元素默认已排序。
3. 内层从后往前扫描，把比 key 大的元素依次后移。
4. 必须用临时变量 key 保存当前要插入的元素。
5. 最好时间复杂度 O(n)，最坏和平均 O(n²)，空间 O(1)。
6. 插入排序是稳定排序。
7. 插入排序的移动次数等于数组中的逆序对数量。
8. 数据基本有序时，插入排序效率极高。
9. 与冒泡相比，插入排序在部分有序时更优；与选择相比，插入排序稳定且最好情况更快。
10. 多练“排序过程模拟”“代码填空”“复杂度与稳定性判断”三类题。

复习建议：先把移动法代码写熟，确保闭卷能默写；再手动模拟 [5, 3, 8, 1]、[6, 2, 9, 4] 等数组的每一轮结果；最后练习“统计逆序对”等综合应用。考试中先判断题目考的是过程、代码、复杂度还是稳定性，再套用对应知识作答。