java堆排序概念原理介绍

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;
  }
}