程序员罕用的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; }}结构堆
把一个输出的数组构建成一个堆有序，咱们有两种形式：
- 从左向右遍历数组，而后把调用swim()上浮操作保障指针右边的元素都是堆有序的，就和优先级队列的插入过一样
- 因为数组中的每个地位曾经是堆的节点，咱们能够从右向左调用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
最初（点关注，不迷路）
文中或者会存在或多或少的有余、谬误之处，有倡议或者意见也十分欢送大家在评论交换。
最初，写作不易，请不要白嫖我哟，心愿敌人们能够点赞评论关注三连，因为这些就是我分享的全副能源起源????