Java 插入排序：抓牌怎么排，它就怎么排

打麻将抓牌时你怎么理牌？插入排序就是那么干的

引言

插入排序（Insertion Sort）最贴近人类日常行为——手里有一副牌，新抓一张，从后往前找到合适位置插进去。

数据越有序，跑得越快。最好情况 O(n)，最差 O(n²)。它不光是希尔排序的基石，更是 JDK Arrays.sort() 的核心组件之一——JDK 对小数组（< 47 个元素）默认就调用插入排序。

这篇文章，我会把插入排序讲透：

• 用 ASCII 图演示”抓牌+理牌”的完整过程
• 推导为什么”搬移元素”比”交换元素”更高效
• 列出 4 个高频易错点（尤其是 while 条件里的 > 号）
• 配套 LeetCode 147（链表插入排序）的工程实战

---

1. 核心思想：抓牌→理牌→再抓牌

1.1 通俗理解

想象你在打麻将，手里已经有了一堆排好序的牌：

手里：1万 3万 5万 7万（已排好序）
新抓：4万
操作：从右往左找，4万 应该插到 3万 和 5万 之间
结果：1万 3万 4万 5万 7万

1.2 ASCII 图解演示

以数组 [5, 2, 4, 6, 1, 3] 为例：

初始：[5, 2, 4, 6, 1, 3]

第 1 趟（i=1，key=2）：
  已排序部分：[5]
  key = 2，j = 0
  arr[0] = 5 > 2，5 往后挪 → [_, 5]
  j = -1，退出循环
  arr[0] = 2
  结果：[2, 5, 4, 6, 1, 3]

第 2 趟（i=2，key=4）：
  已排序部分：[2, 5]
  key = 4，j = 1
  arr[1] = 5 > 4，5 往后挪 → [2, _, 5]
  arr[0] = 2 < 4，停止
  arr[1] = 4
  结果：[2, 4, 5, 6, 1, 3]

第 3 趟（i=3，key=6）：
  已排序部分：[2, 4, 5]
  key = 6，j = 2
  arr[2] = 5 < 6，停止
  arr[3] = 6
  结果：[2, 4, 5, 6, 1, 3]

第 4 趟（i=4，key=1）：
  已排序部分：[2, 4, 5, 6]
  key = 1，j = 3
  arr[3] = 6 > 1，挪 → [2, 4, 5, _, 6]
  arr[2] = 5 > 1，挪 → [2, 4, _, 5, 6]
  arr[1] = 4 > 1，挪 → [2, _, 4, 5, 6]
  arr[0] = 2 > 1，挪 → [_, 2, 4, 5, 6]
  j = -1，退出
  arr[0] = 1
  结果：[1, 2, 4, 5, 6, 3]

第 5 趟（i=5，key=3）：
  已排序部分：[1, 2, 4, 5, 6]
  key = 3，j = 4
  arr[4] = 6 > 3，挪
  arr[3] = 5 > 3，挪
  arr[2] = 4 > 3，挪
  arr[1] = 2 < 3，停止
  arr[2] = 3
  结果：[1, 2, 3, 4, 5, 6]

1.3 三个关键观察

1. 已排序部分逐步扩大——每趟结束后，前面 i+1 个元素一定有序
2. 数据越有序，挪动越少——这就是为什么”基本有序”是插入排序的最佳场景
3. 搬移 vs 交换——一次搬移只移动一个元素（3 步赋值），一次交换要 3 步赋值（操作相同），但交换还会多做一次比较

---

2. 完整 Java 实现

import java.util.Arrays;

public class InsertionSort {
    /**
     * 插入排序（搬移元素版）
     * @param arr 待排序数组（原地修改）
     */
    public static void insertionSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        int n = arr.length;
        // 从第 2 个元素开始（第 1 个视为已排序）
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;
            // 把比 key 大的元素统统往后挪
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            // 插入 key 到正确位置
            arr[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6};
        System.out.println("排序前: " + Arrays.toString(arr));
        insertionSort(arr);
        System.out.println("排序后: " + Arrays.toString(arr));
    }
}

优化空间：上述代码还可以用二分查找找插入位置，减少比较次数（但搬移次数不变），这就是二分插入排序。

---

3. 复杂度证明

3.1 时间复杂度

最坏情况（O(n²)）：数组完全逆序

• 第 1 趟挪 0 次
• 第 2 趟挪 1 次
• …
• 第 n 趟挪 n-1 次
• 总挪动次数 = 0 + 1 + … + (n-1) = n(n-1)/2 = O(n²)

最好情况（O(n)）：数组已经有序

• 每趟都比 1 次就停止
• 总比较次数 = n-1 = O(n)

平均情况（O(n²)）：

• 期望挪动 n²/4 次

3.2 空间复杂度

• **O(1)**，原地排序

3.3 稳定性：稳定

• 比较条件 arr[j] > key（严格大于）
• 相同元素不会挪动
• 稳定排序

---

4. 四个高频易错点

易错点 1：i 从 0 开始

// ❌ 错误：第 0 个元素没有"已排序部分"，key = arr[0]，j = -1
for (int i = 0; i < n; i++) { ... }

// ✅ 正确：从 i=1 开始，第 0 个元素视为已排序
for (int i = 1; i < n; i++) { ... }

易错点 2：while 条件写成 >=

// ❌ 错误：相同元素会挪动 → 不稳定
while (j >= 0 && arr[j] >= key) { ... }

// ✅ 正确：严格大于，保持稳定
while (j >= 0 && arr[j] > key) { ... }

易错点 3：忘记 j >= 0 边界检查

// ❌ 错误：j = -1 时 arr[j] 越界
while (arr[j] > key) {
    arr[j + 1] = arr[j];
    j--;
}

// ✅ 正确：先检查 j >= 0
while (j >= 0 && arr[j] > key) {
    arr[j + 1] = arr[j];
    j--;
}

关键：j >= 0 必须在前面，否则 arr[j] 会先越界。

易错点 4：忘记保存 key

// ❌ 错误：搬移过程中 arr[i] 会被覆盖
for (int i = 1; i < n; i++) {
    int j = i - 1;
    while (j >= 0 && arr[j] > arr[i]) {
        arr[j + 1] = arr[j];
        j--;
    }
    arr[j + 1] = arr[i];  // 此时 arr[i] 已被覆盖！
}

// ✅ 正确：用 key 提前保存
int key = arr[i];
while (j >= 0 && arr[j] > key) { ... }
arr[j + 1] = key;

---

5. JDK 实战：为什么 Arrays.sort() 要用插入排序？

JDK 的 Arrays.sort() 内部对小数组（< 47 个元素）默认调用插入排序，而不是快排。原因是：

5.1 常数因子分析

对于 n=10 的数组：

• 快排：递归调用 + partition 函数 + 栈帧开销 → 实际执行可能比 O(n²) 还慢
• 插入排序：无递归、无栈帧、CPU 缓存友好

5.2 CPU 缓存命中率

插入排序对连续内存顺序访问，CPU 缓存命中率接近 100%。快排的递归分区会跳跃访问，缓存命中率低。

5.3 工程经验法则

数据量小（n < 50）→ 插入排序**
**数据量大（n > 50）→ 快排/归并

这也是为什么各大排序库（如 Python sorted()、C++ std::sort）都有类似的阈值切换。

---

6. 适用场景与禁区

6.1 适用场景

• 数据量小（n < 100）
• 数据基本有序：插入排序的最强战场
• 流式数据：新数据到达时插入到有序列表（在线排序）
• 链表排序：搬移操作变成改指针，效率更高

6.2 不适用场景

• 大数据量乱序：O(n²) 太慢
• 数组 + 大数据量：搬移操作开销大
• 生产环境大数据：用 JDK 的 Arrays.sort()

---

7. 面试常见变形

变形 1：二分插入排序

思路：用二分查找找插入位置，减少比较次数

public static void binaryInsertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int key = arr[i];
        int left = 0, right = i - 1;
        // 二分查找插入位置
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] > key) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        // left 就是插入位置，把 [left, i-1] 整体后挪
        for (int j = i - 1; j >= left; j--) {
            arr[j + 1] = arr[j];
        }
        arr[left] = key;
    }
}

复杂度：比较 O(n log n)，挪动仍是 O(n²)。**整体仍是 O(n²)**，只是减少了比较次数。

变形 2：希尔排序（分组插入排序）

思路：把数组按间隔分组，每组分别插入排序，再缩小间隔

public static void shellSort(int[] arr) {
    int n = arr.length;
    for (int gap = n / 2; gap > 0; gap /= 2) {
        // 对每个分组做插入排序
        for (int i = gap; i < n; i++) {
            int key = arr[i];
            int j = i - gap;
            while (j >= 0 && arr[j] > key) {
                arr[j + gap] = arr[j];
                j -= gap;
            }
            arr[j + gap] = key;
        }
    }
}

复杂度：取决于 gap 序列。Knuth 序列（1, 4, 13, 40…）下达到 O(n^1.5)。

变形 3：链表插入排序

思路：改指针而不是搬移元素

public ListNode insertionSortList(ListNode head) {
    ListNode dummy = new ListNode(0);
    ListNode curr = head;
    while (curr != null) {
        ListNode next = curr.next;
        // 在 dummy 链表中找插入位置
        ListNode p = dummy;
        while (p.next != null && p.next.val < curr.val) {
            p = p.next;
        }
        // 插入 curr
        curr.next = p.next;
        p.next = curr;
        curr = next;
    }
    return dummy.next;
}

优点：链表插入是 O(1)（改指针），整体性能优于数组版本。

---

8. LeetCode 真题实战

题目 1：147. 对链表进行插入排序（中等）

描述：给定单链表的头节点 head，使用插入排序对链表进行排序。

解法：直接套用上面”链表插入排序”变形 3。

复杂度：时间 O(n²)，空间 O(1)。

题目 2：912. 排序数组（中等）

插入排序解法：直接套用模板。

结果：n=50000 时超时，但能展示插入排序的边界控制能力。

---

总结

一句话精髓

插入 = 抓牌 → 从后往前挪 → 找到位置插入。

三个关键洞察

1. 数据越有序，跑得越快——最好 O(n)，这是它最强的特性
2. JDK 小数组默认用它——n < 47 时插入排序实际比快排快
3. 稳定性靠 > 保证——用 >= 会变成不稳定排序

下一步行动

1. 手写二分插入排序，理解”查找 O(log n) + 挪动 O(n)” 的 trade-off
2. 用插入排序解 LeetCode 147（链表版），体会链表插入的优势
3. 在 JDK 源码 Arrays.sort() 里搜索 insertionSort，看看真实的工业代码

---