图解堆排序
发布网友
发布时间：2022-12-30 21:58
共1个回答
热心网友
时间：2023-10-31 18:02
在上一篇中我们一起使用二叉堆实现了优先级队列，假如我们从构建好的优先级队列中持续调用删除最小（或者最大），把结果输出到另一个数组中，那么就可以把数组的所有元素进行排序，这就是本篇我们需要学习的堆排序。在看本篇之前需要先看下前一篇《原来实现优先级队列如此简单》
堆排序的过程主要有两个阶段：
开始之前，我们需要把上一篇中的sink()方法修改一下；
保证我们在进行排序的时候直接使用原始的数组，无需建立一个辅助数组浪费空间；由于我们需要动态的缩小堆的大小，需要把size通过参数传入；
其次我们数组的下标是从0开始的，与之前的优先级排序有些差别，对于k节点的左边节点下标是2k+1，右边下标是2k+2
把一个输入的数组构建成一个堆有序，我们有两种方式：
例如：输入数组 a[]={8,3,6,1,4,7,2}
下沉是堆排序的第二个阶段，我们把最大元素删除，然后放入到堆缩小后数组中空出来的位置，当操作完成所有的元素之后，整个数组将会是有序的
下沉排序演示过程（图未完全画完）：
文中所有源码已放入到了github仓库 https://github.com/silently9527/JavaCore
文中或许会存在或多或少的不足、错误之处，有建议或者意见也非常欢迎大家在评论交流。
最后，写作不易，请不要白嫖我哟，希望朋友们可以点赞评论关注三连，因为这些就是我分享的全部动力来源🙏
