堆排序

先用维基百科的一张动图直观展示一下堆排序过程

bubkoo.qiniudn.com/Sorting_heapsort_anim.gif

1. 什么是堆

这里的堆是一种数据结构，不是内存分配中堆栈的堆。堆是一颗完全二叉树，除了最底层外，每层都是满的，这使得堆可以用数组来表示，每个节点对应数组中的一个元素。

images.cnblogs.com/cnblogs_com/kkun/201111/201111231437369307.png

2. 堆分为最大堆和最小堆：

最大堆是指所有父节点的元素值大于或等于其子元素的值(如果存在的话)，因此最大堆中的最大元素必然是根节点。

最小堆是指所有父节点的元素值小于或等于其子元素的值(如果存在的话)，因此最小堆中的最小元素必然为根节点。

3. 堆中节点与数组索引的对应关系如下：

left[i] = parent[2*i],        right[i] = parent[2*i + 1]

4. 将堆调整为最大堆

images.cnblogs.com/cnblogs_com/kkun/201111/201111231437377256.png

5. 堆排序过程

images.cnblogs.com/cnblogs_com/kkun/201111/201111231437374682.png

以最大堆为例，需要维护最大堆、建立最大堆和进行堆排序，

maxHeapify维护最大堆，是堆排序的关键，时间复杂度为O(lgn)

buildMaxHeap建立最大堆，将无序输入的数组构造为最大堆，时间复杂度为O(nlgn)

heapSort对数据进行原地排序，时间复杂度为O(nlgn)。

java实现堆排序算法代码如下(root的index为0)：

maxHeapify的过程如下图所示：

bubkoo.qiniudn.com/building-a-heap.png

private static void maxHeapify(int[] array, int index, int heapSize) {

int iMax = index;

int iLeft = index *2+1;

int iRight = (index +1) *2;

if(iLeft < heapSize && array[iLeft] > array[iMax]) {

iMax = iLeft;

}

if(iRight < heapSize && array[iRight] > array[iMax]) {

iMax = iRight;

}

if(iMax != index) {

swap(array,iMax,index);

maxHeapify(array,iMax,heapSize);//recurse,递归调整

}

}

//将无序的输入建立为最大堆

private static void buildMaxHeap(int[] array) {

intiParent = array.length/2-1;

for(int i = iParent;i >=0;i--) {

maxHeapify(array,i,array.length);

}

}

堆排序过程如下图所示：

bubkoo.qiniudn.com/HeapSort.png

public static int[] sort(int[] array) {

int[] result = array;

buildMaxHeap(result);

intarrayLength = result.length;

for(inti = arrayLength -1;i >0;i--) {

swap(result,0,i);

maxHeapify(result,0,i);

}

return result;

}

private static void swap(int[] array, int i, int j) {

int tmp = array[i];

array[i] = array[j];

array[j] = tmp;

}