插入排序——像整理手中的牌，把数据排好队

你有没有玩过扑克牌？摸到一张新牌时，你会把它插到手里已经排好序的牌中间，比如从小到大排。插入排序就是模仿这个动作：把数组分成“已排序”和“未排序”两部分，每次从“未排序”里取一个数，把它插到“已排序”中正确的位置上。虽然它不算最快的排序方法，但思路特别自然，数据基本有序时速度飞快，生活中也经常用到。

核心思想：像理牌一样一步步来

假设你左手已经握着几张牌，这些牌已经按从小到大排好了。右手拿起一张新牌，你需要：

从左手牌的最右边开始，一张一张往左比较。
如果新牌比当前牌小，就把当前牌往右挪一个位置。
直到遇到比新牌小的牌（或者左边没有牌了），就把新牌插进去。

在计算机里，数组的第一个元素天然就是“已排序”的（只有一张牌，当然有序）。然后我们从第二个元素开始，重复上面的插入动作。

举个例子：给零食价格排序

小明的零花钱买了几种零食，价格分别是 12, 11, 13, 5, 6 元（数组中的数字）。现在他想按价格从小到大整理。

初始状态：
[12 | 11, 13, 5, 6] 左边竖线左边是“已排序”部分（只有12），右边是“未排序”。

第1步（取11）：

11 和 12 比较，11 < 12，所以 12 向右挪一位（变成 [12, 12, 13, 5, 6] 但注意数组是原地修改）。
然后 11 放到原来 12 的位置，结果：[11, 12 | 13, 5, 6]

第2步（取13）：

13 和 12 比较，13 > 12，13 不动，直接放在末尾。结果：[11, 12, 13 | 5, 6]

第3步（取5）：

5 和 13 比，5 < 13，13 右移 → [11, 12, 13, 13, 6]
5 和 12 比，5 < 12，12 右移 → [11, 12, 12, 13, 6]
5 和 11 比，5 < 11，11 右移 → [11, 11, 12, 13, 6]
左边没有元素了，5 插入到开头 → [5, 11, 12, 13 | 6]

第4步（取6）：

6 和 13 比，6 < 13，13 右移 → [5, 11, 12, 13, 13]
6 和 12 比，6 < 12，12 右移 → [5, 11, 12, 12, 13]
6 和 11 比，6 < 11，11 右移 → [5, 11, 11, 12, 13]
6 和 5 比，6 > 5，停止，6 插入到 5 后面 → [5, 6, 11, 12, 13]

完成！排序后的价格从小到大：5, 6, 11, 12, 13。

生活中的插入排序场景

整理试卷：每次拿到新发的试卷，你会插入到已经按科目或日期排好的试卷堆里，插入到合适位置。
排队按身高：班级里大家随便站，老师让每个人从第二个开始，依次插入到前面已排好的身高队列中（比较一下前面的同学，比自己高就往后让一让）。
整理零花钱账本：每次有一笔新支出，按日期顺序插入到记账本里。

C++ 代码实现（带详细注释）

下面代码用 insertionSort 函数实现插入排序。关键变量都用了简短的英文单词，每行变量定义都有中文注释，方便理解。

#include <iostream>
using namespace std;

void insertionSort(int arr[], int n) {
    // 外层循环：从第二个元素开始，i 是当前要插入的元素下标
    for (int i = 1; i < n; i++) {
        int key = arr[i];      // key：当前要插入的“牌”
        int j = i - 1;         // j：从已排序部分的最后一个位置开始往前找

        // 内层循环：把比 key 大的元素往后挪一个位置
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];  // 把大的元素右移
            j--;                  // 继续往左比较
        }
        // 跳出循环时，j+1 就是 key 应该插入的位置
        arr[j + 1] = key;
    }
}

int main() {
    // 测试数据：零花钱价格
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);   // 计算数组元素个数

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

    insertionSort(arr, n);   // 调用排序函数

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

    return 0;
}

运行结果：

排序前：12 11 13 5 6 
排序后：5 6 11 12 13

插入排序的特点

稳定排序：相同大小的元素，排序后相对顺序不变（比如两个6，原来的先后顺序不会变）。
原地排序：不需要额外数组，只用 O(1) 的额外空间。
时间复杂度：
- 最好情况（数组已经排好序）：每次插入只需比较一次，总比较次数为 n-1，时间复杂度 O(n)。
- 最坏情况（数组完全逆序）：每个元素都要和前面所有元素比较并后移，总比较次数约 n²/2，时间复杂度 O(n²)。
- 平均情况也是 O(n²)。
适用场景：数据量不大（比如几十个），或者数据基本有序时，插入排序非常快。很多高级排序（如快速排序、归并排序）在数据接近有序时也会改用插入排序来提速。

新手常犯的错误

忘记检查 j >= 0
内层循环如果写成 while (arr[j] > key)，当 j 变成 -1 时，会越界访问数组，导致程序崩溃。一定要先判断 j >= 0。
把 key 赋值成了前面的元素
比如把 key = arr[i]; 写成了 key = arr[i-1];，这样就会丢失当前要插入的值。
外层循环从 0 开始
如果 for (int i = 0; i < n; i++)，第一个元素会被当作未排序，导致比较时 j = i-1 = -1，while 进不去，但会浪费一次无意义的循环。正确是从 1 开始。
后移时覆盖了正确的位置
比如先直接写 arr[i] = arr[i-1] 而不保存 key，会导致数据丢失。代码中的做法是先保存 key，然后通过 while 后移，最后插入，这个顺序不能乱。

完整示例：带打印中间过程的版本

如果你想看清每一步的插入过程，可以在代码里加一些打印语句：

#include <iostream>
using namespace std;

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        cout << "第 " << i << " 步：取 key = " << key << endl;

        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;

        // 打印当前数组状态
        cout << "  当前数组：";
        for (int k = 0; k < n; k++) cout << arr[k] << " ";
        cout << endl;
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    insertionSort(arr, n);
    return 0;
}

输出能清楚看到每一步插入后的变化。

插入排序——像整理手中的牌