插入排序：像整理扑克牌一样把新牌插到正确位置

像插扑克牌一样，把新数字放到正确的位置——插入排序

插入排序是一种非常自然的排序方法，就像你玩扑克牌时，每次摸到一张新牌，就会把它插到手牌里合适的位置，让手牌一直保持从小到大（或从大到小）的顺序。在编程里，插入排序也是这样工作的：它把数组分成两部分——左边是已经排好序的，右边是还没排序的。每次从右边拿一个元素，在左边的已排序部分中找到它该放的位置，然后把它插进去。

插入排序特别适合处理数据量不大、或者初始数据已经接近有序的情况。下面我们就一步步来学习它。

一、核心思想：左已排好，右未排，一个一个往里插

想象一下，你手里已经有了一张牌 3，然后又摸到 1。你会怎么放？你会把 1 插到 3 的前面，因为 1 比 3 小。接着摸到 4，它比 3 大，直接放在 3 后面就行。再摸到 2，你会从右往左看，先看到 4 比 2 大，把 4 往后挪一位；再看 3 也比 2 大，把 3 往后挪一位；最后看到 1 比 2 小，所以把 2 插在 1 的后面。

这就是插入排序的完整过程：

• 刚开始，数组的第一个元素（下标0）默认就是已排序部分（只有它一个）。
• 从第二个元素（下标1）开始，依次将每个元素插入到前面的已排序序列中。
• 插入时，先把这个元素存到一个临时变量里，然后从已排序部分的最后一个元素开始，依次比较：如果已排序的元素比临时变量大，就把它往后移一位，直到找到合适的位置，再把临时变量放进去。

二、分步图解：用 [3, 1, 4, 2] 排成从小到大

排序完成！这个过程就像排队时，新来的同学根据身高找到自己的位置，比他高的人依次往后退一步。

三、代码实现：每一行都讲清楚

下面是一段完整的插入排序代码，变量名很简短，每一行都有中文注释，方便你理解。

#include <iostream>
using namespace std;

int main() {
    int arr[] = {3, 1, 4, 2};   // 待排序的数组
    int n = 4;                  // 数组元素个数

    // 从第二个元素开始（下标1）逐个插入到前面已排序部分
    for (int i = 1; i < n; i++) {
        int key = arr[i];       // 要插入的数（临时存起来，防止被覆盖）
        int j = i - 1;          // 从已排序部分的最后一个元素开始比较

        // 把比 key 大的元素都往后挪一位，腾出位置
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];  // 把大的元素往后移
            j--;                  // 继续往前检查
        }
        // 此时 j 指向的位置要么是 -1（说明 key 最小），要么是 arr[j] <= key
        arr[j + 1] = key;         // 把 key 放到空出来的位置
    }

    // 输出排序后的数组
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";    // 依次打印每个元素，空格隔开
    }
    return 0;
}

运行结果：

1 2 3 4

四、常见错误（新手最容易掉进的坑）

1. 忘记用临时变量保存要插入的数
   如果直接写 j = i-1; while (j>=0 && arr[j] > arr[i]) { arr[j+1] = arr[j]; j--; } arr[j+1] = arr[i];，在循环里 arr[j] 可能已经被移动覆盖了 arr[i] 原来的值，导致丢失数据。一定要先 int key = arr[i]; 把它存起来。

2. 循环条件写错

   • 很多人写成 while (j >= 0 && arr[j] > key) 但没注意 j-- 后可能变成负数，条件要同时检查 j >= 0。
   • 或者把 arr[j] > key 写成 arr[j] >= key，这样会破坏排序的稳定性（下面会讲）。一般从小到大排序用 > 即可。

3. 插入位置搞错
   循环结束后，j 已经比目标位置少1，所以最后要放的位置是 j+1。如果写成 arr[j] = key 或者 arr[j+2] = key 都会出错。

4. 忘记从 i=1 开始
   如果 i 从 0 开始，第一个元素会被当作未排序的，但实际它已经是已排序部分了，不需要再处理。

五、插入排序的特点

• 时间复杂度：最坏情况（数组完全逆序，比如 [5,4,3,2,1]）下，每个数都要比较并移动所有前面的数，总操作次数大约是 1+2+...+(n-1)=n(n-1)/2，记作 O(n²)。最好情况（数组已经排好序）下，每个数只需要和前面一个数比较，发现已经有序，直接放最后，时间复杂度为 O(n)。平均情况也是 O(n²)。
• 空间复杂度：只需要一个临时变量 key 和几个循环变量，原地排序，O(1) 额外空间。
• 稳定性：插入排序是稳定的——如果两个相同的数，它们在排序前后的相对顺序不变。因为我们在比较时只有 arr[j] > key 才移动，相等的元素不会交换位置。例如 [3, 3, 1] 排序后，前面的 3 仍然在前。
• 适用场景：数据量很小（比如少于几十个）、或者数据大部分已经有序时，插入排序非常快。很多高级排序算法（如快速排序）在数据量较小的时候，也会改用插入排序来提高效率。

六、生活中的更多例子

• 按考试成绩排名：老师每次拿到一个新同学的成绩，就插到已经排好的成绩单里。
• 整理零花钱：你每天得到一些零钱，把它们按面值从小到大排好（比如先是一角、五角、一元），每次新拿到一枚硬币就插到对应位置。
• 排队打饭：一个新同学来排队，他身高比较矮，于是从队伍后面往前看，找到第一个比他矮的人（或者比他高的人后面），然后插进去，比他高的人都往后挪一步。

七、完整可运行程序（含输入输出）

下面是一个更完整的程序，你可以自己输入数字，看看排序过程。代码里加了详细的注释和中间过程打印（可选）。

#include <iostream>
using namespace std;

int main() {
    int arr[100];               // 假设最多100个数
    int n;                      // 实际要排序的个数

    cout << "请输入要排序的数字个数：";
    cin >> n;

    cout << "请输入 " << n << " 个整数（空格隔开）：";
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    // 插入排序主循环
    for (int i = 1; i < n; i++) {
        int key = arr[i];       // 要插入的数
        int j = i - 1;          // 已排序部分最后一个下标

        // 把比 key 大的数往后移动
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;       // 插入到正确位置

        // 可选的：打印每一轮排序后的结果
        cout << "第 " << i << " 轮插入后：";
        for (int k = 0; k < n; k++) {
            cout << arr[k] << " ";
        }
        cout << endl;
    }

    cout << "最终排序结果：";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

八、相关知识点拓展

• 冒泡排序：也是 O(n²) 的排序，但它是通过相邻元素两两比较交换，把最大的“冒”到最后。插入排序比冒泡排序通常快一些，因为移动次数更少。
• 选择排序：每次在未排序部分中找最小的，放到已排序的末尾。它不稳定，但交换次数少。
• 希尔排序：插入排序的升级版，允许元素跨大步跳跃，先让数组“基本有序”，最后再用插入排序收尾，效率更高。
• 归并排序、快速排序：更高级的 O(n log n) 排序算法，适合大数据量。它们也会在内部数据片段较小时切换到插入排序。

插入排序是你学会的第一个“聪明”的排序：它不靠两两交换，而是靠移动和插入，非常符合人类直觉。掌握了它，你就学会了排序里一个非常重要的思想——有序地插入。