Appearance
插入排序
场景引入
打扑克牌时，你是怎么整理手牌的？每摸到一张新牌，你会从右向左扫描手牌，找到合适的位置插入。这就是插入排序的核心思想。
插入排序虽然平均时间复杂度也是 O(n²)，但它有一个重要特性：对近乎有序的数据极其高效。实际上，Java 的 Arrays.sort() 和 Python 的 sorted() 所使用的 TimSort 算法，其内部就是用插入排序来处理小规模或近乎有序的子数组。
核心思路
插入排序将数组分为已排序部分和未排序部分。每次从未排序部分取出第一个元素，在已排序部分中从后往前找到合适位置，将其插入。
算法步骤
- 将第一个元素视为已排序部分
- 取出未排序部分的第一个元素作为
key - 从已排序部分的末尾开始，逐个与
key比较 - 如果当前元素比
key大，将其向右移动一位 - 直到找到不大于
key的元素（或到达数组头部），将key插入该位置 - 重复步骤 2-5
为什么插入排序比冒泡排序好？
两者都是 O(n²) 的算法，但插入排序有两个关键优势：
- 赋值代替交换：冒泡排序每次交换需要 3 次赋值（临时变量），而插入排序只需 1 次赋值（元素右移）
- 提前终止：找到插入位置后，内层循环立即停止，不需要继续扫描
- 对有序数据友好：已排序数组上插入排序是 O(n)，冒泡排序也是 O(n)，但插入排序常数更小
算法流程图
可视化演示
代码实现
javascript
function insertionSort(arr) {
const n = arr.length;
for (let i = 1; i < n; i++) {
let key = arr[i]; // 待插入的元素
let j = i - 1;
// 将比 key 大的元素依次右移
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key; // 插入到正确位置
}
return arr;
}二分插入排序
在已排序部分中查找插入位置时，可以用二分查找代替线性查找，将比较次数从 O(n) 降到 O(log n)。但元素移动次数不变，整体仍为 O(n²)。
javascript
function binaryInsertionSort(arr) {
const n = arr.length;
for (let i = 1; i < n; i++) {
let key = arr[i];
// 二分查找插入位置
let lo = 0, hi = i;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (arr[mid] > key) hi = mid;
else lo = mid + 1;
}
// 将 [lo, i-1] 的元素右移一位
for (let j = i; j > lo; j--) {
arr[j] = arr[j - 1];
}
arr[lo] = key;
}
return arr;
}复杂度分析
| 时间复杂度 | 空间复杂度 | |
|---|---|---|
| 最好 | O(n) — 已有序，内层循环不执行 | O(1) |
| 平均 | O(n²) | O(1) |
| 最坏 | O(n²) — 完全逆序 | O(1) |
稳定性：稳定。相等元素不会越过彼此（arr[j] > key 用的是严格大于）。
适用场景：
- 数据量小（n < 50 左右）
- 数据基本有序（逆序对数量少）
- 在线排序（数据流式到达，边接收边排序）
面试要点
- 插入排序是稳定的原地排序算法
- 最好情况 O(n)，这是它胜过选择排序的关键
- 理解"哨兵"优化：将
arr[0]作为哨兵，可省去j >= 0的边界检查 - TimSort（JavaScript/Python/Java 标准排序）在小规模子数组上使用插入排序
LeetCode 练习
- LC 912. 排序数组 — 插入排序实现（大数据量会超时，用于学习）
- LC 147. 对链表进行插入排序 — 链表版插入排序
- LC 35. 搜索插入位置 — 二分查找插入位置，与二分插入排序的内层逻辑一致