首页 / 算法 / Java排序算法(五):堆排序
Java排序算法(五):堆排序
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了Java排序算法(五):堆排序,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1689字,纯文字阅读大概需要3分钟。
内容图文
[算法说明]
堆排序是对简单选择排序的改进
简单选择排序是从n个记录中找出一个最小的记录,需要比较n-1次。但是这样的操作并没有把每一趟的比较结果保存下来,在后一趟的比较中,有许多比较在前一趟已经做过了,但由于前一趟排序时未保存这些比较结果,所以后一趟排序时又重复执行了这些比较操作,因而记录的比较次数较多。
堆是具有下列性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆;或者每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆。
[算法思想]
将待排序的序列构造成一个大顶堆。此时,整个序列的最大值就是堆顶的根节点。将它移走(其实就是将其与堆数组的末尾元素交换,此时末尾元素就是最大值),然后将剩余的n-1个序列重新构造成一个堆,这样就会得到n个元素中的次最大值。如此反复执行,就能得到一个有序序列了。
[java实现]
public class HeapSort { public static void main(String[] args) { int[] arr = { 6, 5, 3, 1, 8, 7, 2, 4 }; System.out.println("排序之前:"); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } // 堆排序 heapSort(arr); System.out.println(); System.out.println("排序之后:"); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } } /** * 堆排序 */ private static void heapSort(int[] arr) { for (int i = arr.length / 2; i >= 0; i--){ // 将待排序的序列构建成一个大顶堆 heapAdjust(arr, i, arr.length); } for (int i = arr.length - 1; i > 0; i--) { // 逐步将每个最大值的根节点与末尾元素交换,并且再调整其成为大顶堆 swap(arr, 0, i); // 将堆顶记录和当前未经排序子序列的最后一个记录交换 heapAdjust(arr, 0, i); } } private static void heapAdjust(int[] arr, int i, int n) { int child; int tmp; for (tmp = arr[i]; leftChild(i) < n; i = child) { child = leftChild(i); if (child != n - 1 && arr[child] < arr[child + 1]) { child++; } if (tmp < arr[child]) { arr[i] = arr[child]; } else { break; } } arr[i] = tmp; } private static int leftChild(int i) { return 2 * i + 1; } private static void swap(int[] arr, int index1, int index2) { int tmp = arr[index1]; arr[index1] = arr[index2]; arr[index2] = tmp; } }[算法总结]
堆排序时间复杂度:O(nlogn)
堆排序对原始记录的排序状态并不敏感,其在性能上要远远好过于冒泡、简单选择、直接插入排序。
原文:http://blog.csdn.net/zdp072/article/details/44227317
内容总结
以上是互联网集市为您收集整理的Java排序算法(五):堆排序全部内容,希望文章能够帮你解决Java排序算法(五):堆排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。