插入排序

插入排序就像我们摸扑克牌：手里的牌已经理好，新摸一张就从右往左一张张比，比它大的牌都往右挪一格腾出空位，再把新牌插进去。数组里也一样，把每个数当成"新摸的牌"，往前面已排好的部分里插。

#include <iostream>
using namespace std;
int main() {
    int a[5] = {5, 3, 8, 1, 9}, n = 5;
    for (int i = 1; i < n; i++) {
        int key = a[i], j = i - 1;
        while (j >= 0 && a[j] > key) { a[j + 1] = a[j]; j--; }
        a[j + 1] = key;                     // 找到位置插进去
    }
    for (int x : a) cout << x << ' ';       // 1 3 5 8 9
}

新手常忘了先用 key 把 a[i] 存起来，直接往后挪就把要插的数覆盖丢了。记住：先存牌，再挪位，最后插。