堆排序 介绍：
堆排序可以分为两个阶段。在堆的构造阶段，我们将原始数组重新组织安排进一个堆中；然后在下沉排序阶段，我们从堆中按顺序取出所有元素并得到排序结果。
1.堆的构造，一个有效的方法是从右到左使用sink()下沉函数构造子堆。数组的每个位置都有一个子堆的根节点，sink()对于这些子堆也适用，如果一个节点的两个子节点都已经是堆了，那么在该节点上调用sink()方法可以把他们合并成一个堆。我们可以跳过大小为1的子堆，因为大小为1的不需要sink()也就是下沉操作，有关下沉和上浮操作可以参考我写的优先队列那篇。
2.堆的排序，我们通过第一步操作构造了一个堆，在这个堆中，根节点永远是最大值的节点，所以我们把根节点的值与数组最后的值进行交换，在使用sink()下沉来维护堆的结构即可。
具体代码实现:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
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; } } |
运行结果: