CSP-J/S冲奖第21天:插入排序
一、插入排序概念
1.1 生活中的类比
o 扑克牌排序：就像整理手中的扑克牌，每次将一张牌插入到已排好序的牌中合适位置
o 动态演示：
初始序列：[5, 2, 4, 6, 1, 3]
排序过程：
→ [2, 5, 4, 6, 1, 3]
→ [2, 4, 5, 6, 1, 3]
→ ... → [1, 2, 3, 4, 5, 6]
1.2 算法特点
| 特性 | 说明 |
|---|---|
| 时间复杂度 | 平均 O(n^2)，最好 O(n)，最坏 O(n^2) |
| 空间复杂度 | O(1)（原地排序） |
| 稳定性 | 稳定排序算法 |
| 适用场景 | 小规模数据/部分有序数据 |
二、算法实现步骤
2.1 核心思想
将数组分为已排序区间和未排序区间 初始时已排序区间只包含第一个元素 每次从未排序区间取一个元素，在已排序区间找到合适位置插入 重复直到所有元素有序
2.2 详细步骤
对于 i 从 1 到 n-1： 1. 将 arr[i] 存入临时变量 temp 2. 从 i-1 开始向前遍历，将比 temp 大的元素后移 3. 找到合适位置后插入 temp
三、C++代码实现
3.1 基础版本
#include <iostream>
using namespace std;
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int temp = arr[i];
int j = i - 1;
// 将比temp大的元素后移
while (j >= 0 && arr[j] > temp) {
arr[j+1] = arr[j];
j--;
}
arr[j+1] = temp; // 插入正确位置
}
}
int main() {
int arr[] = {5, 2, 4, 6, 1, 3};
int n = sizeof(arr)/sizeof(arr[0]);
insertionSort(arr, n);
cout << "排序结果：";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}
3.2 运行结果
排序结果：1 2 3 4 5 6
四、算法解析
4.1 关键代码分析
while (j >= 0 && arr[j] > temp) {
arr[j+1] = arr[j];
j--;
}
边界条件： j >= 0防止数组越界移动操作：比当前元素大的值逐个后移 插入位置：循环结束后 j+1 即为正确位置
4.2 性能优化
o 提前终止：当元素已在正确位置时，可提前结束内层循环
o 二分查找优化：使用二分查找确定插入位置（减少比较次数，移动次数不变）
五、常见错误与调试
5.1 典型错误
| 错误类型 | 示例代码 | 解决方案 |
|---|---|---|
| 数组越界 | int j = i（初始值错误） | 确保 j 初始值为 i-1 |
| 丢失元素 | 忘记赋值 arr[j+1] = temp | 保证最后执行插入操作 |
| 无限循环 | while (j > 0) 缺少终止条件 | 添加 j >= 0 边界判断 |
5.2 调试技巧
打印中间过程：
cout << "第" << i << "轮排序：";
for (int k=0; k<n; k++) cout << arr[k] << " ";
cout << endl;
单元测试：
// 测试完全逆序数组
int test1[] = {5,4,3,2,1};
// 测试已有序数组
int test2[] = {1,2,3,4,5};
六、实战练习
6.1 基础题
题目：实现降序排列的插入排序
参考代码：
void insertionSortDesc(int arr[], int n) {
for (int i = 1; i < n; i++) {
int temp = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] < temp) { // 修改比较方向
arr[j+1] = arr[j];
j--;
}
arr[j+1] = temp;
}
}
6.2 进阶题
题目：统计插入排序过程中元素移动的总次数
实现思路：
int insertionSortCount(int arr[], int n) {
int count = 0;
for (int i = 1; i < n; i++) {
int temp = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > temp) {
arr[j+1] = arr[j];
j--;
count++; // 每次移动计数
}
arr[j+1] = temp;
}
return count;
}
七、复杂度分析
| 情况 | 时间复杂度 | 说明 |
|---|---|---|
| 最好 | O(n) | 初始有序，只需遍历无需移动 |
| 平均 | O(n^2) | 需要约 n^2/4 次比较和移动 |
| 最坏 | O(n^2) | 逆序时需要 n^2/2 次操作 |
| 空间复杂度 | O(1) | 只需要常数级额外空间 |
