堆排序(java)

堆排序(java)

   堆排序适合于大量数据的排序，堆排序的前续工作花费的时间比较多，下面我们以大根堆为例说说：
大根堆，就是根节点是最大的元素，所以每次把最大的元素选出来，与最后的一个元素交换，然后再把前n-1个元素（也就是除最后一个元素）进行一个堆的重构，让其具有大根堆的性质，重复上面的过程，直到只剩一个元素为止。这个过程其实是个选择排序的过程，但是少了交换的次数，堆排序的时间复杂度是nlogn。

下面是我写的demo程序，仅供参考：

public class HeapSort {

 /**
  * 维持一个大根堆的性质
  * 
  * @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;
 }

 /**
  * 
  * 堆排序 
  * 原理：每次把最大的元素（即：堆根）与最后一个元素交换，
  * 然后把前n-1个元素进行堆的重构,直到只剩一个元素为止。
  * 
  * 
  * @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);
  
 }
}

文章来自:http://blog.163.com/lazy_p/blog/static/13510721620104715715445/