堆排序是一种基于「堆」这一数据结构的排序算法。堆是一种近似完全二叉树的结构，分为大顶堆和小顶堆这两种。
- 大顶堆：子节点的值总是小于其父节点的值。
- 小顶堆：子节点的值总是大于其父节点的值。
如果使用大顶堆的话，最后的排序结果会是升序；如果采用小顶堆的话，最后的排序结果会是降序。
使用大顶堆实现数字大小排序
首先会使用大顶堆来实现数字的从小到大排序，主要分为下面 3 个过程：
- 最大堆调整：将堆的末端子节点做调整，使得子节点小于父节点。
- 创建最大堆：将堆中所有数据排序成大顶堆的形式。
- 堆排序：将顶端数据和最末尾数据交换位置，然后做最大堆调整的递归运算。
实现代码如下所示：
使用小顶堆实现字符串大小排序
和大顶堆的过程一样，只是有些微小的差别：
- 最小堆调整：将堆的末端子节点做调整，使得子节点大于父节点。
- 创建最大堆：将堆中所有数据排序成小顶堆的形式。
- 堆排序：将顶端数据和最末尾数据交换位置，然后做最小堆调整的递归运算。
实现代码如下所示：
具体代码可见这个 repo 中的 Homework-4 和 mid-exam。
参考：
[1]. 堆排序 - 维基百科
[2]. 图解排序算法(三)之堆排序
网友评论