插入排序认为待排序数组可视作"已排好序的前缀 + 未排序的后缀"。每次从后缀中取出一个元素的 key，把它插入到前缀中适当位置。

Ph1zの理解： 打扑克牌时，你每摸一张牌，就从右往左找到它该插的位置，插进去——这就是插入排序。手牌始终有序，每张新牌只是"插入"到正确位置。

代码

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

正确性证明：循环不变式

循环不变式： 在外层循环每轮开始时，a[0..i-1] 已经有序，并且恰好包含原数组中前 i 个元素的所有值。

• 初始化： i = 1 时，a[0] 显然有序；不变式成立。
• 保持： 设当前 key = a[i]，内层循环把所有大于 key 的元素右移，直到找到正确插入位置 j + 1，此时前缀 a[0..i] 仍然有序。
• 终止： 当 i = n 时，整个数组有序。

Ph1zの理解： 循环不变式就像"归纳假设"——你要证明三件事：开始时对、每步保持对、结束时恰好是你想要的。数学归纳捏

因此插入排序是正确的。 ✓

复杂度分析

情况	时间复杂度	直觉
最好	$O(n)$	数组本来有序，key 每次直接放回原位，内层循环几乎不执行
最坏	$O(n^2)$	逆序，每个 key 要一直移到最前面，内层循环执行 $i$ 次
平均	$O(n^2)$	随机数据，key 平均要移动 $i/2$ 次

空间复杂度： $O(1)$。

稳定性： 稳定。因为只有 a[j] > key 时才右移，等于 key 的元素不移动，故相同关键字顺序保持。

插入排序的实战价值： 虽然理论上是 $O(n^2)$，但对近乎有序的数组极快（接近 $O(n)$），而且常数因子极小。所以很多高级排序（如 TimSort）在小段或近乎有序段会退回插入排序——不是"落后"，而是"精明"。