时间:2021-05-19
堆排序介绍:
堆排序可以分为两个阶段。在堆的构造阶段,我们将原始数组重新组织安排进一个堆中;然后在下沉排序阶段,我们从堆中按顺序取出所有元素并得到排序结果。
1.堆的构造,一个有效的方法是从右到左使用sink()下沉函数构造子堆。数组的每个位置都有一个子堆的根节点,sink()对于这些子堆也适用,如果一个节点的两个子节点都已经是堆了,那么在该节点上调用sink()方法可以把他们合并成一个堆。我们可以跳过大小为1的子堆,因为大小为1的不需要sink()也就是下沉操作,有关下沉和上浮操作可以参考我写的优先队列那篇。
2.堆的排序,我们通过第一步操作构造了一个堆,在这个堆中,根节点永远是最大值的节点,所以我们把根节点的值与数组最后的值进行交换,在使用sink()下沉来维护堆的结构即可。
具体代码实现:
public class PQSort{ public static void main(String[] args){ int[] a = {9,1,7,5,3,9,12,56,21,45}; sort(a); for(int i=0;i<a.length;i++) { System.out.print(a[i]+" "); } } //排序方法 public static void sort(int[] a){ int N = a.length-1; //通过下沉操作构造堆,因为下标从0开始,所以子节点为2*k+1和2*k+2; for(int k = (N-2)/2;k>=0;k--){ sink(a,k,N); } //通过不断把堆中最大值放到数组的后面来排序 while(N>0){ exch(a,0,N--); sink(a,0,N); } } //下沉函数 private static void sink(int[] a, int i, int n){ while(2*i+1<=n){ int j = 2*i+1; if(j<n&&a[j]<a[j+1]) j++; if(a[i]>a[j]) break; exch(a,i,j); i=j; } } //交换函数 private static void exch(int[] a, int i, int j){ int temp = a[i]; a[i] = a[j]; a[j] = temp; }}运行结果:
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
这篇文章主要介绍了Java如何实现八个常用的排序算法:插入排序、冒泡排序、选择排序、希尔排序、快速排序、归并排序、堆排序和LST基数排序,分享给大家一起学习。分
本文通过一个C语言实现堆排序的简单实例,帮助大家抛开复杂的概念,更好的理解堆排序。实例代码如下:voidFindMaxInHeap(intarr[],const
本文实例讲述了php堆排序实现原理与应用方法。分享给大家供大家参考。具体分析如下:这里以php作为描述语言较详细讲解堆排序原理,因保证程序可读性,故不做优化,p
本文实现了八个常用的排序算法:插入排序、冒泡排序、选择排序、希尔排序、快速排序、归并排序、堆排序和LST基数排序首先是EightAlgorithms.java文
本文实例为大家分享了C语言堆排序源代码,供大家参考,具体内容如下1.堆排序堆排序的定义及思想可以参考百度百科:用一句概括,堆排序就是一种改进的选择排序,改进的地