插入排序 Insertion Sort
插入排序 · 像整理手里的扑克牌
什么是插入排序
插入排序就是理牌的过程：左手里的牌始终有序，每次从右边摸一张新牌（key），从右往左和已有序的牌逐个比较，找到位置插进去。数组里的做法一样——把左侧前缀维护成有序区，逐个把后面的元素插入到前缀的正确位置。它实现简单、常数小，在小数据或近乎有序的数据上表现相当好。
它怎么做
第 i 轮取出 key = a[i]（玫红高亮），在左边有序前缀里边比较边右移：比 key 大的元素依次向右让位，直到腾出 key 该在的空位落下。点「下一步」看 [7, 6, 5, 10, 9, 8, 4, 3, 2, 1]：玫红的 key 一路向左「滑」到位，左侧有序区每轮扩大一格。
第 1 轮：取出 key=6
1function insertionSort(a: number[]): number[] {
2 const n = a.length;
3 for (let i = 1; i < n; i++) {
4 const key = a[i];
5 let j = i - 1;
6 while (j >= 0 && a[j] > key) {
7 a[j + 1] = a[j];
8 j--;
9 }
10 a[j + 1] = key;
11 }
12 return a;
13}
n10
i1
key6
j0
a[j]7
shiftCount0
sortedUpTo1
1 / 94
复杂度与适用
时间 O(n²)、常数额外空间、稳定。它的亮点是自适应：数据越接近有序，每轮要移动的越少——完全有序时退化为一趟 O(n) 扫描。正因如此，它常被当作更复杂排序的「小数组子程序」（如 TimSort、IntroSort 在小段上转用插入排序）。
比较是瓶颈？二分插入排序用折半查找定位插入点，把每轮的比较从 O(n) 降到 O(log n)（移动仍在）。
移动是瓶颈？希尔排序先按大间隔分组插入，让元素大步归位，跳出 O(n²)。
移动是瓶颈？希尔排序先按大间隔分组插入，让元素大步归位，跳出 O(n²)。
两个改进方向本站都有页：二分插入排序省比较、希尔排序省移动——对照着看，能清楚「插入」这个动作还能怎么优化。