关于排序学习:图解堆排序

程序员罕用的 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}

下沉排序

下沉是堆排序的第二个阶段，咱们把最大元素删除，而后放入到堆放大后数组中空进去的地位，当操作实现所有的元素之后，整个数组将会是有序的

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

堆排序代码实现

@Override
public 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

最初（点关注，不迷路）

文中或者会存在或多或少的有余、谬误之处，有倡议或者意见也十分欢送大家在评论交换。

最初，写作不易，请不要白嫖我哟 ，心愿敌人们能够 点赞评论关注 三连，因为这些就是我分享的全副能源起源????