排序算法系列 04：插入排序——打牌的人都会
插入排序是我个人觉得最"人性化"的排序算法。为什么这么说？因为你打扑克的时候，整理手牌用的就是这个思路——摸一张新牌，从右往左看，找到它该待的位置，插进去。
别看它也是 O(n²)，在数据量小或者数据基本有序的时候，插入排序跑得比很多"高级"算法都快。这也是为什么 V8、Python 的 TimSort 在小数组时都会切到插入排序。
核心思想
把数组分成"已排序"和"未排序"两部分。每次从未排序部分拿一个元素，插入到已排序部分的正确位置。
text
初始：5 | 2, 9, 1, 7 （竖线左边是已排序区）
插入 2：2, 5 | 9, 1, 7
插入 9：2, 5, 9 | 1, 7
插入 1：1, 2, 5, 9 | 7
插入 7：1, 2, 5, 7, 9
怎么"插入"的？
不是真的把元素抽出来再塞进去（那样数组要整体移动）。实际做法是：
- 记住当前要插入的元素
current - 从它前面的元素开始往左看
- 比
current大的元素依次往后挪一位 - 找到合适位置后，把
current放进去
就像打牌时，你把新牌悬在手里，然后把比它大的牌一张张往右推，腾出空位再放下。
代码实现
javascript
function insertionSort(arr) {
const result = [...arr];
for (let i = 1; i < result.length; i++) {
const current = result[i];
let j = i - 1;
while (j >= 0 && result[j] > current) {
result[j + 1] = result[j];
j--;
}
result[j + 1] = current;
}
return result;
}
console.log(insertionSort([5, 2, 9, 1, 7]));
// [1, 2, 5, 7, 9]
几个要点：
- 从
i = 1开始，因为第一个元素自己就是"有序的" current先存起来，给后面的挪动腾地方while循环做的事情就是"把大的往后推"- 循环结束后
j + 1就是current该待的位置
复杂度
| 情况 | 时间复杂度 |
|---|---|
| 最好（已有序） | O(n) |
| 平均 | O(n²) |
| 最坏（完全逆序） | O(n²) |
最好情况是 O(n) 这一点很关键。如果数组本身已经基本有序，内层 while 几乎不执行，整个排序接近线性。这是冒泡和选择都做不到的（选择排序即使有序也得 O(n²)）。
空间复杂度 O(1)。
稳定性：稳定。相等元素不会越过彼此——因为条件是 result[j] > current，相等时不挪动。
为什么实际工程里还在用它？
你可能觉得 O(n²) 的东西没什么用。但实际上，插入排序在以下场景非常能打：
- 小数组（比如 10~20 个元素）：算法的常数开销很小，比递归调用快排还快
- 几乎有序的数据：接近
O(n)，碾压绝大多数算法 - 作为复合排序的组件：TimSort 在子数组长度 < 64 时用的就是插入排序
所以它不是"学完就扔"的算法，在很多高性能排序实现的底层都能看到它的身影。
和冒泡、选择的对比
三个 O(n²) 排序放一起看：
| 冒泡 | 选择 | 插入 | |
|---|---|---|---|
| 核心动作 | 相邻交换 | 选最小值 | 插入到有序区 |
| 最好情况 | O(n) | O(n²) | O(n) |
| 稳定性 | 稳定 | 不稳定 | 稳定 |
| 实际用途 | 纯教学 | 纯教学 | 小数组优化 |
如果只能记一个简单排序算法，记插入排序。
下一篇来看希尔排序——它就是在插入排序基础上的一次聪明改良。
系列导航