java堆排序概念原理介绍

java堆排序概念原理介绍

堆排序介绍：

堆排序可以分为两个阶段。在堆的构造阶段，我们将原始数组重新组织安排进一个堆中；然后在下沉排序阶段，我们从堆中按顺序取出所有元素并得到排序结果。

1.堆的构造，一个有效的方法是从右到左使用sink()下沉函数构造子堆。数组的每个位置都有一个子堆的根节点，sink()对于这些子堆也适用，如果一个节点的两个子节点都已经是堆了，那么在该节点上调用sink()方法可以把他们合并成一个堆。我们可以跳过大小为1的子堆，因为大小为1的不需要sink()也就是下沉操作，有关下沉和上浮操作可以参考我写的优先队列http://那篇。

2.堆http://的排序，我们通过第一步操作构造了一个堆，在这个堆中，根节点永远是最大值的节点，所以我们把根节点的值与数组最后的值进行交换，在使用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

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

http://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;

}

}

运行结果:

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

http://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;

}

}

运行结果:

http://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;

}

}

运行结果:

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。