图解堆排序
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了图解堆排序,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2080字,纯文字阅读大概需要3分钟。
内容图文
![图解堆排序](/upload/InfoBanner/zyjiaocheng/1035/5ab39b4df5eb46fdac0d7dd9714cc9f4.jpg)
程序员常用的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}
下沉排序
下沉是堆排序的第二个阶段,我们把最大元素删除,然后放入到堆缩小后数组中空出来的位置,当操作完成所有的元素之后,整个数组将会是有序的
下沉排序演示过程(图未完全画完):
堆排序代码实现
@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
最后(点关注,不迷路)
文中或许会存在或多或少的不足、错误之处,有建议或者意见也非常欢迎大家在评论交流。
最后,写作不易,请不要白嫖我哟,希望朋友们可以点赞评论关注三连,因为这些就是我分享的全部动力来源
内容总结
以上是互联网集市为您收集整理的图解堆排序全部内容,希望文章能够帮你解决图解堆排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。