堆排序 (Heap Sort)

用柱状动画看堆排序先建最大堆,再把最大值逐个送到末尾。O(n log n) 且 O(1) 空间,却为何很少被采用。

算法

数组

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

比较

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)。但父子访问跳跃大、缓存不友好且不稳定,实践中输给快排 — 不过优先队列内部至今仍是它。 排序可视化

常见问题

什么是堆?
父节点恒大于子节点的完全二叉树(最大堆)。用数组表示时 i 的子节点是 2i+1、2i+2,无需指针。
堆排序实际用在哪里?
内存极受限的环境、需要最坏情况保证的场景、取前 K 个元素,以及优先队列的内部实现。

其他算法