插入排序模板

#include <bits/stdc++.h>
using namespace std;

int main() {
    int a[] = {5, 3, 8, 1, 2};
    int n = 5;

    // 插入排序
    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 x : a) cout << x << " ";  // 1 2 3 5 8
    cout << endl;

    return 0;
}

📖 要点说明

• 时间复杂度 O(n²)，最好 O(n)（已排序时）
• 思路：摸牌整理——新牌插入已排好牌的正确位置
• 稳定排序：相等元素不移动，相对位置不变
• 对近乎有序的数据效率很高，接近 O(n)

⚠️ 常见错误

• 外层从 i=1 开始不是 0
• while 条件 j >= 0 忘了，导致越界
• 移位后忘在正确位置赋值 key