堆排序
复习
- 堆：父不大于子，堆顶是最值
- 优先队列：每次取出优先级最高的元素
- 数组：堆可以用数组紧凑表示
TL;DR
- 堆排序先把数组建成堆，再反复取出堆顶
- 每取出一个，就把剩下的部分重新调整成堆
- 时间稳定在
O(n log n)，并且就地排序 - 它是基于比较的排序，通常不稳定
正文
我们学过堆，也学过用堆实现优先队列。把这两样东西用到排序上，就得到了堆排序（heapsort）。
反复取堆顶
堆的特点是：堆顶永远是最值。 堆排序就抓住这一点：
- 先把整个数组整理成一个堆（比如最大堆，堆顶是最大值）
- 把堆顶（最大值）和末尾元素交换，这样最大值就放到了它最终的位置
- 把堆的有效范围缩小一格，再对新的堆顶做“下沉”，恢复堆的性质
- 重复，直到堆里只剩一个元素
每次取出一个最大值放到末尾，从后往前，数组就逐渐有序了。整个过程就像是用优先队列不断地“弹出最值”，只不过是在同一个数组里就地完成。
稳定的 O(n log n)
建堆的过程可以做到 O(n)；之后要取出 n 个元素，每次取出后调整堆是 O(log n)，合计 O(n log n)。
更重要的是：这个代价是稳定的，不像快排会因基准不佳而退化。无论输入怎样，堆排序都保持 O(n log n)。
代价与缺点
堆排序的优点是就地——不需要像归并那样额外开一个数组，也不像快排有最坏退化。
代价则在于：它虽然就地，却不像快排那样对缓存友好——访问的元素在数组里跳来跳去。而且它是不稳定的，相等的元素在反复交换中可能被打乱顺序。
于是，三种 O(n log n) 排序各有性格：
- 归并：稳定、最坏也稳定，但要额外空间
- 快排：就地、平均最快，但最坏会退化、不稳定
- 堆排：就地、最坏稳定，但常数偏大、不稳定
没有全能的选手，只有各适其用的工具。 这也正是这几章反复想传达的观念。
思考题 1
堆排序是怎样利用堆“堆顶是最值”这一性质的？
思考题 2
堆排序可以就地完成，它的代价是什么？
小结
知识点
- 堆排序先建堆，再反复取出堆顶
- 每轮把堆顶与末尾交换，再缩小堆并调整
- 时间稳定为
O(n log n)，就地完成 - 常数较大且不稳定
参考资料
- Wikipedia(zh)：堆排序：利用堆进行排序的算法
- Wikipedia(zh)：二叉堆：堆排序依赖的结构
思考题答案（仅供参考）
思考题 1
因为堆顶始终是当前堆里的最大（或最小）值。堆排序反复取出堆顶，就相当于不断取出当前最大值，把它放到最终位置，再调整剩余部分，从而完成排序。
思考题 2
代价主要是：堆内元素的访问位置跳来跳去，对缓存不够友好，常数偏大；而且它是基于比较、通常不稳定，相等元素的相对顺序可能被打乱。就地省下了空间，却付出了这些代价。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪