堆排序(java)

   堆排序適合于大量數(shù)據(jù)的排序，堆排序的前續(xù)工作花費(fèi)的時(shí)間比較多，下面我們以大根堆為例說說：
大根堆，就是根節(jié)點(diǎn)是最大的元素，所以每次把最大的元素選出來，與最后的一個(gè)元素交換，然后再把前n-1個(gè)元素（也就是除最后一個(gè)元素）進(jìn)行一個(gè)堆的重構(gòu)，讓其具有大根堆的性質(zhì)，重復(fù)上面的過程，直到只剩一個(gè)元素為止。這個(gè)過程其實(shí)是個(gè)選擇排序的過程，但是少了交換的次數(shù)，堆排序的時(shí)間復(fù)雜度是nlogn。

下面是我寫的demo程序，僅供參考：

public class HeapSort {

 /**
  * 維持一個(gè)大根堆的性質(zhì)
  * 
  * @param heap
  * @param from
  * @param to
  */
 private static void keepHeap(int[] a, int n, int i) {
  int x = a[i];
  int j = 2 * i + 1;
  while (j <= n - 1) {
   if (j < n - 1 && a[j] < a[j + 1])
    ++j;
   if (a[j] > x) {
    a[i] = a[j];
    i = j;
    j = 2 * i + 1;
   } else
    break;
  }
  a[i] = x;
 }

 /**
  * 
  * 堆排序 
  * 原理：每次把最大的元素（即：堆根）與最后一個(gè)元素交換，
  * 然后把前n-1個(gè)元素進(jìn)行堆的重構(gòu),直到只剩一個(gè)元素為止。
  * 
  * 
  * @param a
  */
 private static void heapSort(int[] a) {
  int n = a.length;
  while (n > 0) {
   int tmp = a[0];
   a[0] = a[n - 1];
   a[n - 1] = tmp;
   keepHeap(a, --n, 0);
  }
 }

 public static void main(String[] args) {
  

  int[] ar = new int[1000000];
  for (int i = 0; i < 1000000; ++i) {
   ar[i] = (int) (Math.random() * 1000001);
  }
  int n = ar.length;

  long b = System.currentTimeMillis();
  for (int i = ((n >> 1) - 1); i >= 0; --i) {
   keepHeap(ar, n, i);
  }

  heapSort(ar);

  System.out.println(System.currentTimeMillis() - b);
  
 }
}