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 算法特点

二、算法实现步骤

2.1 核心思想

1. 将数组分为已排序区间和未排序区间
2. 初始时已排序区间只包含第一个元素
3. 每次从未排序区间取一个元素，在已排序区间找到合适位置插入
4. 重复直到所有元素有序

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 典型错误

5.2 调试技巧

1. 打印中间过程：

cout << "第" << i << "轮排序：";
for (int k=0; k<n; k++) cout << arr[k] << " ";
cout << endl;

2. 单元测试：

// 测试完全逆序数组
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;
}

七、复杂度分析