【考点 · 4级】插入排序——基础排序算法，属于排序 + 交换类考点。
【说人话】
想象你打扑克牌——手里的牌已经排好序，每摸一张新牌就从右往左找到合适位置插进去。这就是插入排序的核心：把数组分成"已排序"和"未排序"两部分，每次从未排序区取一个，插入已排序区的正确位置。
时间复杂度：最好 O(n)（已经有序时），最坏 O(n²)（完全逆序时）。空间复杂度 O(1)，是原地排序。
j >= 0 && a[j] > key，别忘了 j >= 0 防越界！② 关键值 key 先暂存，不是直接交换，而是边移动边腾位置；③ 插入排序是稳定排序（相同元素不改变相对顺序），这是它比冒泡排序的优势。
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n; cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
// 插入排序
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; // 插入正确位置
}
for (int i = 0; i < n; i++)
cout << a[i] << (i < n-1 ? " " : "\n");
return 0;
}
1️⃣ key 必须先暂存——别直接用 a[i] 比较然后移动，移动过程中 a[i] 的值会被覆盖！
2️⃣ j >= 0 不能省——当 key 比所有元素都小时，j 会减到 -1，不判断就数组越界了。
3️⃣ 是"腾位置"不是"交换"——插入排序每轮把大元素统一右移一步，最后把 key 放进去。交换法（swap相邻）也能排但效率差一倍。
4️⃣ 稳定 vs 不稳定——插入排序是稳定的，冒泡排序也是。选择排序是不稳定的。考试爱考这个区别！
5️⃣ 适用场景——插入排序在 n 很小或数据基本有序时优于快排，C++ STL 的 sort 内部对小区间就会切换到插入排序。