排序 · 单步演示
堆排序
把数组看成一棵完全二叉树，先整理成大顶堆（每个结点都不小于孩子），堆顶就是最大值；把它换到末尾，堆缩小一格，再让新的堆顶往下沉，重复到堆里只剩一个数。
当前操作已就位
步 001 / 084初始数组。把数组看成一棵完全二叉树：a[i] 的孩子是 a[2i+1] 和 a[2i+2]。先建大顶堆，再反复把堆顶换到末尾。
键盘：← → 单步，空格 播放/暂停（先点一下演示区）。
伪代码 · 当前行高亮
for i ← ⌊n/2⌋−1 down to 0：下沉(i, n)for end ← n−1 down to 1交换 a[0]、a[end]下沉(0, end)下沉(i, size)：largest ← i；l ← 2i+1；r ← 2i+2if l < size 且 a[l] > a[largest]：largest ← lif r < size 且 a[r] > a[largest]：largest ← rif largest ≠ i：交换 a[i]、a[largest]；i ← largest；回到上一步
变量
| 比较次数 | 0 |
|---|---|
| 交换/写入次数 | 0 |
复杂度
| 最好情况 | O(n log n) |
|---|---|
| 平均情况 | O(n log n) |
| 最坏情况 | O(n log n) |
| 额外空间 | O(1) |
| 稳定性 | 不稳定 |
自底向上建堆总共是 O(n)；之后 n−1 次取堆顶，每次下沉最多走树高 log₂n 层。全程在原数组里做，不需要额外空间。
要点
- 下标关系：a[i] 的孩子是 a[2i+1]、a[2i+2]，父亲是 a[⌊(i−1)/2⌋]。
- 建堆从最后一个有孩子的结点 ⌊n/2⌋−1 开始往前做，叶子不用处理。
- 最坏情况也是 O(n log n)，且不需要额外数组。
常见错误
下沉时只和左孩子比、忘了右孩子，堆性质就会被破坏，排出来的结果会错。