本课时有配套视频讲解，购买后即可观看（永久有效）
插入排序
一、课上练习
编程练习
二、知识总结
✨ 插入排序的核心思想
对一组线性存储的数据进行排序。
插入排序通过插入的方法构建有序序列从而实现排序。就像打牌时整理手牌一样，每次拿到一张新牌，将它插入到手中已排好序的牌的正确位置。插入排序是使用了贪心法的排序算法。
✨ 插入排序的原理
插入排序的执行步骤如下：
- 初始化：将第一个元素视为已排序部分
- 找到未排序部分的第一个元素 X
- 在已排序部分中从后向前查找，找到第一个不大于 X 的元素 Y：
- 若 Y 存在，则将 X 插入到 Y 之后
- 否则将 X 插入到所有元素之前
- 重复步骤 2-3，直到所有元素都已排序
在实现时，通过将大于 X 的元素逐个后移来腾出插入位置，避免了显式的插入操作。
从小到大排序
插入排序从小到大代码示例
1#include <bits/stdc++.h>
2using namespace std;
3
4int arr[1005];
5
6int main() {
7 int n;
8 cin >> n;
9 for (int i = 0; i < n; ++i) {
10 cin >> arr[i];
11 }
12 for (int i = 1; i < n; ++i) {
13 int key = arr[i];
14 int j = i - 1;
15 while (j >= 0 && key < arr[j]) {
16 arr[j + 1] = arr[j];
17 --j;
18 }
19 arr[j + 1] = key;
20 }
21 for (int i = 0; i < n; ++i) {
22 cout << arr[i] << (i + 1 == n ? "\n" : " ");
23 }
24 return 0;
25}从大到小排序
只需将比较条件从 < 改为 >，每次将较小的元素向后移动：
插入排序从大到小代码示例
1#include <bits/stdc++.h>
2using namespace std;
3
4int arr[1005];
5
6int main() {
7 int n;
8 cin >> n;
9 for (int i = 0; i < n; ++i) {
10 cin >> arr[i];
11 }
12 for (int i = 1; i < n; ++i) {
13 int key = arr[i];
14 int j = i - 1;
15 while (j >= 0 && key > arr[j]) {
16 arr[j + 1] = arr[j];
17 --j;
18 }
19 arr[j + 1] = key;
20 }
21 for (int i = 0; i < n; ++i) {
22 cout << arr[i] << (i + 1 == n ? "\n" : " ");
23 }
24 return 0;
25}✨ 插入排序的复杂度分析
| 指标 | 值 |
|---|---|
| 时间复杂度 | O(n^2) |
| 空间复杂度 | O(1) |
| 稳定性 | 稳定排序 |
插入排序的时间复杂度为 O(n^2)，因为最坏情况下每个元素都需要与前面所有元素比较。空间复杂度为 O(1)，只需要常数级别的额外空间。插入排序是稳定的排序算法，因为相等元素不会被交换位置。对于近乎有序的数据，插入排序的效率接近 O(n)，表现优于选择排序和冒泡排序。
✨ 插入排序的执行示例
以数组 [5, 3, 8, 1, 2] 为例，展示从小到大的插入排序完整过程：
初始状态
已排序部分：[5]，未排序部分：[3, 8, 1, 2]
第1轮（i=1）：插入 key=3
| 步骤 | 操作 | 数组状态 |
|---|---|---|
| 比较 | 3 < arr[0]=5? 是 | - |
| 后移 | arr[0]=5 后移到 arr[1] | [5, 5, 8, 1, 2] |
| 插入 | j=-1，将 3 插入 arr[0] | [3, 5, 8, 1, 2] |
已排序：[3, 5]，未排序：[8, 1, 2]
第2轮（i=2）：插入 key=8
| 步骤 | 操作 | 数组状态 |
|---|---|---|
| 比较 | 8 < arr[1]=5? 否 | - |
| 插入 | j=1，将 8 插入 arr[2]（原位置不变） | [3, 5, 8, 1, 2] |
已排序：[3, 5, 8]，未排序：[1, 2]
第3轮（i=3）：插入 key=1
| 步骤 | 操作 | 数组状态 |
|---|---|---|
| 比较 | 1 < arr[2]=8? 是 | - |
| 后移 | arr[2]=8 后移到 arr[3] | [3, 5, 8, 8, 2] |
| 比较 | 1 < arr[1]=5? 是 | - |
| 后移 | arr[1]=5 后移到 arr[2] | [3, 5, 5, 8, 2] |
| 比较 | 1 < arr[0]=3? 是 | - |
| 后移 | arr[0]=3 后移到 arr[1] | [3, 3, 5, 8, 2] |
| 插入 | j=-1，将 1 插入 arr[0] | [1, 3, 5, 8, 2] |
已排序：[1, 3, 5, 8]，未排序：[2]
第4轮（i=4）：插入 key=2
| 步骤 | 操作 | 数组状态 |
|---|---|---|
| 比较 | 2 < arr[3]=8? 是 | - |
| 后移 | arr[3]=8 后移到 arr[4] | [1, 3, 5, 8, 8] |
| 比较 | 2 < arr[2]=5? 是 | - |
| 后移 | arr[2]=5 后移到 arr[3] | [1, 3, 5, 5, 8] |
| 比较 | 2 < arr[1]=3? 是 | - |
| 后移 | arr[1]=3 后移到 arr[2] | [1, 3, 3, 5, 8] |
| 比较 | 2 < arr[0]=1? 否 | - |
| 插入 | j=0，将 2 插入 arr[1] | [1, 2, 3, 5, 8] |
排序完成：[1, 2, 3, 5, 8]
观察规律：
- 每轮取出一个元素，在已排序部分中从右往左找到合适位置插入
- 如果待插入元素本身就比前面所有元素大，则不需要后移，直接原位不动（如第2轮的 8）
- 如果数据本身接近有序，大多数元素只需少量比较就能找到位置，效率很高
✨ 插入排序的解题步骤
例题：将一个新元素插入到已排序数组中，保持有序
这是插入排序单轮操作的直接应用。
示例： 已有有序数组 [1, 3, 5, 7, 9]，插入元素 4。
解题步骤：
- 保存待插入元素：key = 4
- 从右往左扫描，找到第一个不大于 key 的位置：
- arr[4]=9 > 4，后移 → [1, 3, 5, 7, , 9]（ 表示空出的位置）
- arr[3]=7 > 4，后移 → [1, 3, 5, _, 7, 9]
- arr[2]=5 > 4，后移 → [1, 3, _, 5, 7, 9]
- arr[1]=3 <= 4，停止
- 插入到位置 2：[1, 3, 4, 5, 7, 9]
1// 在有序数组 arr[0..n-1] 中插入 key，数组长度变为 n+1
2void insertSorted(int arr[], int &n, int key) {
3 int j = n - 1;
4 while (j >= 0 && key < arr[j]) {
5 arr[j + 1] = arr[j];
6 --j;
7 }
8 arr[j + 1] = key;
9 ++n;
10}✨ 插入排序的常见错误
- 后移方向搞错：插入时应该从右往左扫描，把大于 key 的元素往右移。如果从左往右移，会把数据覆盖丢失
- 忘记保存 key：在后移元素之前必须用
int key = arr[i]保存待插入的值，否则arr[i]会被后移的元素覆盖 - while 循环条件缺少边界检查：
while (j >= 0 && key < arr[j])中的j >= 0不能省略，否则当 key 是最小值时，j 会变成 -1 导致数组越界 - 使用
<=而不是<进行比较：key < arr[j]时才后移，如果写成key <= arr[j]，相等的元素也会被后移，导致相等元素的相对顺序改变，破坏稳定性 - 外层循环从 i=0 开始：应该从
i=1开始，因为第一个元素本身就是有序的，不需要插入