优点:同时最优利用时间和空间的方法
缺点:无法利用缓存(不理解啊~)
public class HeapSort {
private static void heapSort(int[] a){
int n = a.length-1;
//前半部分sink()就可以保证堆有序
for(int k=n/2;k >= 1;k--){
sink(a,k,n);
}
while (n > 1){
a[n] = a[1];
a[1] = a[--n];
sink(a,1,n);//找出下一个最大的
}
}
private static void sink(int[] a,int k,int n){
while (2*k <= n){
int j = 2*k;
if(j < n && (a[j] < a[j+1])) j++;
if(a[k] > a[j]) break;
int temp = a[k];
a[k] = a[j];
a[j] = temp;
k = j;
}
}
public static void main(String[] args){
int[] a = {0,2,493,74,903,58,60,94,58,13,74,93,86,3};
heapSort(a);
for(int i:a)
System.out.print(i+", ");
}
}
