🃏 插入排序 (Insertion Sort)

归档: #Algorithm #Sorting #Elementary

核心心法: "理扑克牌" —— 摸一张新牌，在手里已经排好的牌里找到位置插进去。

🧠 核心思想

将数组分为“已排序区间”和“未排序区间”。

• 每次从未排序区间取出一个元素（新牌）。
• 在已排序区间从后往前扫描，找到合适的位置插入。
• 越有序，越快！

🎨 图解演示

点击“开始排序”体验理牌过程

12

0

11

1

13

2

5

3

6

4

7

5

3

6

15

7

2

8

💻 代码实现 (C++)

void insertionSort(vector<int>& nums) {
    int n = nums.size();
    // 第 0 张牌默认是有序的，从第 1 张开始摸牌
    for (int i = 1; i < n; i++) {
        int key = nums[i]; // 🃏 摸起这张新牌
        int j = i - 1;     // 盯着它前面的那张牌
        
        // 只要前面的牌(j)比新牌(key)大，前面的牌就往后挪
        while (j >= 0 && nums[j] > key) {
            nums[j + 1] = nums[j]; // 往后挪一格
            j--; // 继续往前看
        }
        // 这里的 j+1 就是留出来的空位，把 key 插进去
        nums[j + 1] = key;
    }
}

📊 复杂度分析

维度	数值	说明
时间 (平均)		逆序时很慢
时间 (最好)		数组基本有序时，几乎不用挪动，飞快！
空间		原地操作
稳定性	✅ 稳定	只有严格大于才移动，相等的不动

💡 适用场景

• 小规模数据：当 时，它甚至比快排还快（STL sort 内部就这么干）。

• 基本有序的数组：效率极高，甚至接近 。