每日一练：直接插入排序（C++）

直接插入排序（Insertion Sort）像整理扑克：左手已有有序牌，右手每拿一张就插入到正确位置。它简单、稳定，在 近乎有序 或 n 很小 时非常实用，也是理解更复杂排序的基础。

算法过程

对数组 a[0..n-1]：

1. 假设前缀 a[0..j-1] 已有序
2. 取 key = a[j]
3. 把比 key 大的元素向右挪
4. 把 key 放入空位
5. j 从 1 扫到 n-1

C++ 实现

#include <iostream>
using namespace std;

void insertionSort(int* a, int n) {
    for (int j = 1; j < n; ++j) {
        int key = a[j];
        int i = j - 1;
        while (i >= 0 && a[i] > key) {
            a[i + 1] = a[i];
            --i;
        }
        a[i + 1] = key;
    }
}

int main() {
    int num[10] = {1, 8, 5, 9, 7, 6, 2, 3, 4, 0};
    insertionSort(num, 10);
    for (int m = 0; m < 10; ++m) cout << num[m] << ' ';
    cout << '\n';
    return 0;
}

复杂度与性质

练习延伸

1. 改成降序
2. 统计移动次数
3. 对链表实现插入排序
4. 了解希尔排序如何分组插入以改进性能

小结

插入排序代码短、好证不变式，适合做每日一练的第一题。工程上 n 大时请用 std::sort，但面试手写插入/快排/归并仍是基本功。

模拟一步

数组 [3, 1, 4, 2]：

1. j=1 key=1 → 插入前得 [1, 3, 4, 2]
2. j=2 key=4 → 已有序前缀无需大挪
3. j=3 key=2 → 前移 4,3 得 [1, 2, 3, 4]

稳定排序例子

相等元素相对顺序不变，适合「先按成绩排，再按报名序号排」的多关键字场景（插入作为基础稳定算法理解很好）。

与标准库

C++ std::sort 通常不是纯插入；但 std::stable_sort 与小数组调优路径里仍可能见到插入思想。理解插入，有助于读混合排序实现。