用柱状动画看堆排序先建最大堆,再把最大值逐个送到末尾。O(n log n) 且 O(1) 空间,却为何很少被采用。
算法
数组
比较
0
交换/写入
0
步数
0/665
读取
0
辅助内存
0
递归深度
1/1
放慢速度,用「单步」对照伪代码高亮和柱条颜色。 灰色柱条是已从堆中取出并确定位置的元素。
伪代码
build max-heap (siftDown n/2→0)
for end ← n−1 down to 1
swap a[0] ↔ a[end] // 최댓값 확정
siftDown(0, end)
// child = 2·i+1, 2·i+2 중 큰 쪽과 비교
// 부모 < 자식이면 교환하며 내려감
时间复杂度
| 最好 | O(n log n) |
|---|---|
| 平均 | O(n log n) |
| 最坏 | O(n log n) |
| 空间 | O(1) |
| 稳定 | 否 |
堆排序把数组看作完全二叉堆(i 的子节点为 2i+1、2i+2),先整理成父大于子的最大堆,再把堆顶最大值与末尾交换确定,剩余部分恢复堆性质(sift-down),循环往复。
建堆 O(n),每次提取 O(log n),所有情况 O(n log n),额外空间 O(1)。但父子访问跳跃大、缓存不友好且不稳定,实践中输给快排 — 不过优先队列内部至今仍是它。 排序可视化