思路
取堆的一半后，分解最小子堆 （使用sink()，如果子结点有比父结点大的值的话 取较大子结点和父结点交换，满足堆的性质），然后递归往上取父结点（父结点和其子结点使用sink()，使满足堆的性质），这样一直到根结点，这样就构造了一个堆
交换根结点和最后一个结点，堆的规模-1，然后新的根结点下沉（重新满足堆，根结点是当前堆的最大值）
注意
堆的第一个元素为空 N = this.a.length - 1;
public class HeapSort<K extends Comparable<K>> {
public K[] a;
//N 是去掉第一个元素之后 元素的个数
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++) {
}
}
