像整理扑克牌一样,把每个元素插入左侧已排序区间。近乎有序时接近 O(n) 的原因一看就懂。
算法
数组
比较
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 等混合排序在短区间切换插入排序正是这个原因。稳定且原地排序。 排序可视化