堆排序
先用维基百科的一张动图直观展示一下堆排序过程
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;
}
