《野牛程序员·算法启蒙课》之——插入排序，像打扑克牌一样排序！

✨ 用故事讲给孩子听：

还记得打扑克牌的时候怎么理牌吗？

是不是每拿到一张新牌，就在手上的牌里找合适的位置插进去，让整排扑克牌从小到大排好队？

插入排序就是这个意思：一边看数据，一边把它们“插”进一个排好队的序列里！

🧠 一句话记住插入排序：

把每个元素插入到前面已经排好序的“有序区”中。

📚 步骤就像这样：

• 第一个元素：默认已经排好了（自己一个人当然有序）

• 看第二个元素，插到前面合适的位置

• 看第三个，插到前面排好队的位置中

• 一直到最后一个……

👇 图解举个例子：

原始数组是：
【5, 3, 8, 6, 2】

1. 第一个数 5，默认有序

2. 第二个数 3，比 5 小 → 插到前面 → 【3, 5, 8, 6, 2】

3. 第三个数 8，比前面的都大 → 不动

4. 第四个数 6，比 8 小，比 5 大 → 插到中间 → 【3, 5, 6, 8, 2】

5. 最后一个 2，最小 → 插到最前面 → 【2, 3, 5, 6, 8】

完美 ✅

🧑‍💻 C++代码登场：

#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;

        // 往前找插入位置（从右往左“比大小”）
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];  // 把大的元素往后挪
            j--;
        }

        arr[j + 1] = key;  // 插进去
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; ++i)
        cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int data[] = {5, 3, 8, 6, 2};
    int length = sizeof(data) / sizeof(data[0]);

    cout << "排序前：";
    printArray(data, length);

    insertionSort(data, length);

    cout << "排序后：";
    printArray(data, length);

    return 0;
}

✅ 插入排序的优点：

🌟 排序过程中几乎不交换数据，只是“挪位”，非常节省开销
🌟 对于“差不多有序”的数组特别快！
🌟 理解门槛低，小朋友容易学会！

📣 小朋友任务卡：

试试自己写一段程序，帮老师把 [4, 1, 7, 2, 6] 排一排~
可以用纸和笔先写步骤，再试着打代码，做个小小算法师！