一、插入排序概念摘要：•扑克牌排序：就像整理手中的扑克牌，每次将一张牌插入到已排好序的牌中合适位置•动态演示：初始序列：[5, 2, 4, 6, 1, 3]排序过程：→ [2, 5, 4, 6, 1, 3]→ [2, 4, 5, 6, 1, 3]→ ... → [1, 2, 3,
1.1 生活中的类比
• 扑克牌排序：就像整理手中的扑克牌，每次将一张牌插入到已排好序的牌中合适位置
• 动态演示：
初始序列：[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 算法特点
二、算法实现步骤2.1 核心思想
将数组分为已排序区间和未排序区间初始时已排序区间只包含第一个元素每次从未排序区间取一个元素，在已排序区间找到合适位置插入重复直到所有元素有序2.2 详细步骤
对于 i 从 1 到 n-1： 1. 将 arr[i] 存入临时变量 temp 2. 从 i-1 开始向前遍历，将比 temp 大的元素后移 3. 找到合适位置后插入 temp三、C++代码实现3.1 基础版本
#includeusingnamespacestd;
voidinsertionSort(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; // 插入正确位置
}
}
intmain{
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] << " ";
}
return0;
}
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 性能优化
• 提前终止：当元素已在正确位置时，可提前结束内层循环
• 二分查找优化：使用二分查找确定插入位置（减少比较次数，移动次数不变）
5.1 典型错误
5.2 调试技巧
打印中间过程：cout << "第" << i << "轮排序：";for (int k=0; k
单元测试：// 测试完全逆序数组
int test1 = {5,4,3,2,1};
// 测试已有序数组
int test2 = {1,2,3,4,5};
六、实战练习
6.1 基础题
题目：实现降序排列的插入排序
参考代码：
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 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;
}
七、复杂度分析
来源：王者瑕古今天发糖了吗
