学会堆排序只需要几分钟

之前我写过一篇数据结构的文章：堆其实是个很简单的数据结构。

堆排序，顾名思义，是要借助堆这种数据结构来实现对数据项的排序。在堆这种数据结构中，节点大于或等于自己的子节点，正因为堆有这种特点，所以我们可以将待排序的数据项依次添加到堆中，然后再依次取出根节点。

从堆中取出来的数据项是从大到小排列的，因为根节点永远是最大的，而堆中永远是取根节点。下面来看下堆排序的具体实现（也可以参考堆这个数据结构的代码）

public class HeapSort {
 private int[] array;
 private int currentIndex;
 private int maxSize;
 public HeapSort(int size) {
   maxSize = size;
   array = new int[maxSize];
   currentIndex = 0;
 }
 //插入数据项，并排好序
 public void insertSort(int[] source) {
   for(int i = 0; i < source.length; i++) {
     array[currentIndex] = source[i]; //插入到节点尾
     tickedUp(currentIndex++); //向上重新排好序，使得满足堆的条件
   }
 }
 private void tickedUp(int index) {
   int parentIndex = (index - 1) / 2; //父节点的索引
   int temp = array[index]; //将新加的尾节点存在temp中
   while(index > 0 && array[parentIndex] < temp) {
     array[index] = array[parentIndex];
     index = parentIndex;
     parentIndex = (index - 1) / 2;
   }
   array[index] = temp;
 }
 
 //取出最大值
 public int getMax() {
   int maxNum = array[0];
   array[0] = array[--currentIndex];
   trickleDown(0);
   return maxNum;
 }
 private void trickleDown(int index) {
   int top = array[index];
   int largeChildIndex;
   while(index < currentIndex/2) { //while node has at least one child
     int leftChildIndex = 2 * index + 1;
     int rightChildIndex = leftChildIndex + 1;
     //find larger child
     if(rightChildIndex < currentIndex &&  //rightChild exists?
         array[leftChildIndex] < array[rightChildIndex]) {
       largeChildIndex = rightChildIndex;
     }
     else {
       largeChildIndex = leftChildIndex;
     }
     if(top >= array[largeChildIndex]) {
       break;
     }
     array[index] = array[largeChildIndex];
     index = largeChildIndex;
   }
   array[index] = top;
 }
}

算法分析：堆中插入和取出的时间复杂度均为 O(logN)，所以堆排序算法的时间复杂度为 O(logN)，但是堆排序也需要额外的和待排序序列大小相同的存储空间。其空间复杂度为 O(N)。