思路
取堆的一半后，分解最小子堆 （使用sink()蔑舞，如果子結點有比父結點大的值的話 取較大子結點和父結點交換疯特，滿足堆的性質(zhì)）兴喂，然后遞歸往上取父結點（父結點和其子結點使用sink()荆姆，使?jié)M足堆的性質(zhì)）蒙幻，這樣一直到根結點，這樣就構造了一個堆
交換根結點和最后一個結點胆筒，堆的規(guī)模-1邮破，然后新的根結點下沉（重新滿足堆，根結點是當前堆的最大值）
注意
堆的第一個元素為空 N = this.a.length - 1;
public class HeapSort<K extends Comparable<K>> {
public K[] a;
//N 是去掉第一個元素之后 元素的個數(shù)
int N ;
public HeapSort (){
}
@SuppressWarnings("unchecked")
public HeapSort (K[] a){
this.a = (K[]) new Comparable[a.length + 1];
for (int i = 0; i < a.length; i++) {
this.a[i+1] = a[i];
}
N = this.a.length - 1;
}
public void sort(){
// int N = a.length-1;
for(int k = N/2; k > 0; k--){
sink( k, N);
}
while(N > 0){
System.out.println(N);
exch( 1, N--);
sink( 1, N);
}
System.out.println("");
}
private void exch(int i, int j) {
K tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
private boolean less(int j, int i) {
return a[j].compareTo(a[i]) < 0 ? true : false;
}
private void sink(int k, int n) {
while(2 * k <= n){
int x = 2 * k;
if(x < n && less(x, x + 1)){
x++;
}
if(!less(k, x)){
break;
}
exch(x, k);
k = x;
}
}
}
@Test
public void test01(){
Integer[] a = {5, 6, 2, 3, 1, 4};
HeapSort<Integer> heapSort = new HeapSort<Integer>(a);
heapSort.sort();
for (int i = 0; i < 6; i++) {
}
}
