图解堆排序

程序员常用的 IDEA 插件：https://github.com/silently9527/ToolsetIdeaPlugin

完全开源的淘客项目：https://github.com/silently9527/mall-coupons-server

微信公众号：贝塔学 Java

前言

在上一篇中我们一起使用二叉堆实现了优先级队列，假如我们从构建好的优先级队列中持续调用删除最小（或者最大），把结果输出到另一个数组中，那么就可以把数组的所有元素进行排序，这就是本篇我们需要学习的堆排序。在看本篇之前需要先看下前一篇《原来实现优先级队列如此简单》

堆排序的过程主要有两个阶段：

• 把原始数据构造成一个有序堆（构造堆）

• 从堆中按照递减顺序取出所有元素就可以得到排序结果（下沉排序）

开始之前，我们需要把上一篇中的 sink()方法修改一下；

保证我们在进行排序的时候直接使用原始的数组，无需建立一个辅助数组浪费空间；由于我们需要动态的缩小堆的大小，需要把 size 通过参数传入；

其次我们数组的下标是从 0 开始的，与之前的优先级排序有些差别，对于 k 节点的左边节点下标是 2k+1，右边下标是 2k+2

private void sink(Comparable[] queue, int k, int size) {while (2 * k + 1 < size) {int i = 2 * k + 1;if (i < size - 1 && less(queue[i], queue[i + 1])) {i++;}if (less(queue[i], queue[k])) {break;}exch(queue, i, k);k = i;}}

构造堆

把一个输入的数组构建成一个堆有序，我们有两种方式：

1. 从左向右遍历数组，然后把调用 swim()上浮操作保证指针左边的元素都是堆有序的，就和优先级队列的插入过一样

2. 由于数组中的每个位置已经是堆的节点，我们可以从右向左调用 sink()下沉操作构造堆，这个过程我们可以跳过子堆为 1 的元素，所以我们只需要扫描数组的一半元素。这种方式会更高效。

例如：输入数组 a[]={8,3,6,1,4,7,2}

下沉排序

下沉是堆排序的第二个阶段，我们把最大元素删除，然后放入到堆缩小后数组中空出来的位置，当操作完成所有的元素之后，整个数组将会是有序的

下沉排序演示过程（图未完全画完）：

堆排序代码实现

@Overridepublic void sort(Comparable[] array) {int size = array.length;for (int k = size / 2; k >= 0; k--) {sink(array, k, size);}while (size > 0) {exch(array, 0, --size);sink(array, 0, size);}}

文中所有源码已放入到了 github 仓库https://github.com/silently9527/JavaCore

最后（点关注，不迷路）

文中或许会存在或多或少的不足、错误之处，有建议或者意见也非常欢迎大家在评论交流。

最后，写作不易，请不要白嫖我哟，希望朋友们可以点赞评论关注三连，因为这些就是我分享的全部动力来源🙏