插入排序（Insertion Sort）就是整理手牌的过程：左手里的牌始终是有序的，每次从牌堆顶摸一张新牌，从右往左比较，把它插到正确的位置。对应到数组上，把序列分成「已排序前缀」和「未排序后缀」，逐个取未排序部分的第一个元素（记为 key），在已排序前缀里从后向前扫描，比 key 大的元素依次右移一格，腾出位置后把 key 放入。
对长度为 n 的序列，执行过程是：
a[1] 作为 key 插入前缀 a[0..1]；a[2] 作为 key 插入前缀 a[0..2]……a[i-1] → a[0]，凡大于 key 的右移一格，遇到不大于 key 的位置（或到头部）就把 key 放下；前缀每轮增长一格，n-1 轮后整体有序。柱子颜色就是状态语言（页面右侧也有图例）：
a[0..i]，从左往右生长；a[j-1]；动画下方有一行实时解说（如 a[0] = 38 > key，右移到 a[1]、key = 25 插入 a[2] 就位），结束时汇总总比较次数与右移次数。可以注意观察：比较次数与移动次数是分开计数的——右移的总次数正是序列「逆序对」数量的量级，越接近有序的输入，插入排序越快。
| 项目 | 复杂度 | 说明 |
|---|---|---|
| 平均/最坏时间 | O(n²) | 逆序输入时，第 i 轮要比较、右移 i 次 |
| 最好时间 | O(n) | 序列本身有序时，每轮只比较一次即就位 |
| 空间 | O(1) | 只需 key 一个辅助变量，原地排序 |
| 稳定性 | 稳定 | 只有「大于 key 才右移」，相等元素不会跨越，相对次序保持 |
#include <iostream>
#include <vector>
using namespace std;
// 插入排序：把 a[i] 插入已排序的 a[0..i)
void insertionSort(vector<int>& a) {
int n = a.size();
for (int i = 1; i < n; i++) {
int key = a[i]; // 摸出的新牌
int j = i;
while (j > 0 && a[j - 1] > key) {
a[j] = a[j - 1]; // 比 key 大的右移一格
j--;
}
a[j] = key; // 放入空出的位置
}
}
int main() {
vector<int> a = {5, 2, 9, 1, 7, 3, 8, 4};
insertionSort(a);
for (int x : a) cout << x << ' '; // 输出：1 2 3 4 5 7 8 9
cout << endl;
return 0;
}
插入排序平均 O(n²)，大数据量下不如快速排序、归并排序。但它有两大实用价值：一是对「基本有序」的数据接近 O(n)，常作为 O(n log n) 排序（如 std::sort 的小区间策略、TimSort）的底层配件；二是实现简单、稳定、原地，是理解「增量构造解」思想的入门范例。CSP-J 阶段的「扑克牌理牌」「链表插入」等题都是它的变体。