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

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 实现

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