优点:同时最优利用时间和空间的方法

缺点:无法利用缓存(不理解啊~)

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+", ");
    }

}