先用維基百科的一張動圖直觀展示一下堆排序過程
bubkoo.qiniudn.com/Sorting_heapsort_anim.gif
1. 什么是堆
這里的堆是一種數(shù)據(jù)結(jié)構(gòu)，不是內(nèi)存分配中堆棧的堆折剃。堆是一顆完全二叉樹玻褪，除了最底層外舔箭，每層都是滿的和二，這使得堆可以用數(shù)組來表示掏击，每個節(jié)點對應(yīng)數(shù)組中的一個元素铃在。
images.cnblogs.com/cnblogs_com/kkun/201111/201111231437369307.png
2. 堆分為最大堆和最小堆：
最大堆是指所有父節(jié)點的元素值大于或等于其子元素的值(如果存在的話)，因此最大堆中的最大元素必然是根節(jié)點拢驾。
最小堆是指所有父節(jié)點的元素值小于或等于其子元素的值(如果存在的話)，因此最小堆中的最小元素必然為根節(jié)點改基。
3. 堆中節(jié)點與數(shù)組索引的對應(yīng)關(guān)系如下：
left[i] = parent[2*i], ? ? ? ?right[i] = parent[2*i + 1]
4. 將堆調(diào)整為最大堆
images.cnblogs.com/cnblogs_com/kkun/201111/201111231437377256.png
5. 堆排序過程
images.cnblogs.com/cnblogs_com/kkun/201111/201111231437374682.png
以最大堆為例繁疤，需要維護(hù)最大堆、建立最大堆和進(jìn)行堆排序秕狰，
maxHeapify維護(hù)最大堆稠腊，是堆排序的關(guān)鍵，時間復(fù)雜度為O(lgn)
buildMaxHeap建立最大堆鸣哀，將無序輸入的數(shù)組構(gòu)造為最大堆架忌，時間復(fù)雜度為O(nlgn)
heapSort對數(shù)據(jù)進(jìn)行原地排序，時間復(fù)雜度為O(nlgn)我衬。
java實現(xiàn)堆排序算法代碼如下(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,遞歸調(diào)整
}
}
//將無序的輸入建立為最大堆
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;
}
