堆排序
先把列表整理成堆，也就是每个父节点都比子节点大的树。然后反复把最大值移到末尾。
- 最佳 Ω(n log n)
- 平均 Θ(n log n)
- 最差 O(n log n)
- 内存 O(1)
- 不稳定
- 无需额外内存
这些是什么意思？
- 最佳：输入对这个算法最容易时，时间随列表大小 n 增长的方式。
- 平均：时间随 n 的一般增长。n² 表示值的个数翻倍时耗时约为四倍；n log n 增长得慢得多。
- 最差：最难的输入下的增长。适合速度绝不能下降的场合。
- 内存：除列表外还需要多少额外内存。1 表示几个变量，n 表示一份列表副本。
- 稳定：两个相等的值保持原来的顺序。按记录的某个字段排序时很重要。
- 无需额外内存：直接在列表内部排序，不用第二个列表。
- 比较中
- 移动中
- 已就位
比较次数 交换次数
点击播放，线条会显示排序过程中代价如何增长
点击播放，或一步一步查看。
空格键：播放或暂停。左右方向键：单步移动。Home 和 End 键：跳转。
试试看： 选一个逆序的列表。建堆几乎不需要交换，之后每一轮都把最大值移到末尾。
工作原理
堆就存放在列表里：位置 i 上的值，它的子节点在位置 2i+1 和 2i+2，最大值总在最前面。把它交换到末尾，让堆缩小一格，再修复堆。排好的部分从右边逐渐变长。
适用场合
适合最坏情况下也要保持快速、又不能用额外内存的场合，比如小型设备。平均来说它比快速排序慢，所以常被当作保底方案。