堆排序(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);   }}