插入排序 (Insertion Sort)

像整理扑克牌一样,把每个元素插入左侧已排序区间。近乎有序时接近 O(n) 的原因一看就懂。

算法

数组

大小48
比较中交换/写入枢轴/基准读取已排序
速度50×

比较

0

交换/写入

0

步数

0/1,373

读取

0

辅助内存

0

递归深度

1/1

放慢速度,用「单步」对照伪代码高亮和柱条颜色。

伪代码

for i ← 1 to n−1

key ← a[i], j ← i−1

while j ≥ 0 and a[j] > key

a[j+1] ← a[j], j ← j−1

a[j+1] ← key

时间复杂度

最好O(n)
平均O(n²)
最坏O(n²)
空间O(1)
稳定是

插入排序从第二个元素开始,逐个取出(key),把左侧已排序区中比它大的值右移,再插入空位 — 和整理手牌一样。

最坏 O(n²),但近乎有序时每元素移动很少,实际接近 O(n)。Timsort 等混合排序在短区间切换插入排序正是这个原因。稳定且原地排序。 排序可视化

常见问题

插入排序什么时候快?
数组小(约 50 个以内)或近乎有序时最快 — 生产级混合排序在短分区都用它。
是稳定排序吗?
是。只移动严格更大的值,相等键保持顺序。

其他算法