排序 · 单步演示
插入排序
把数组分成左边有序、右边待处理两段。每次从右边拿一个数，在左边从后往前找位置，比它大的都往右挪一格，再把它放进空出来的位置。
当前操作已就位
步 001 / 047初始数组。左边第一个数单独看是有序的，之后把每个数插进左边的有序段。
键盘：← → 单步，空格 播放/暂停（先点一下演示区）。
伪代码 · 当前行高亮
for i ← 1 … n−1key ← a[i]；j ← i−1while j ≥ 0 且 a[j] > keya[j+1] ← a[j]；j ← j−1a[j+1] ← key结束
变量
| 比较次数 | 0 |
|---|---|
| 交换/写入次数 | 0 |
复杂度
| 最好情况 | O(n) |
|---|---|
| 平均情况 | O(n²) |
| 最坏情况 | O(n²) |
| 额外空间 | O(1) |
| 稳定性 | 稳定 |
输入已经有序时，每个 key 只比较一次就停下，总共 n−1 次比较。输入完全逆序时，第 i 个数要挪 i 次，总共约 n²/2 次。
要点
- 挪动次数等于逆序对个数：数据「基本有序」时它非常快。
- 很多语言的标准库在子数组很短时会改用插入排序，因为常数小。
- 条件写成 a[j] > key（严格大于），相等时不越过，所以稳定。
常见错误
把条件写成 a[j] ≥ key 仍能排对，但相等元素会被挪到前面，排序就不稳定了。