1. 簡述

??? 假設(shè)待排序數(shù)組為 int array[], 數(shù)組長度為n。
??? 主要是利用堆的性質(zhì)。對(duì)于升序排序，使用最大堆。
??? 首先，建堆，使用遞歸后根序遍歷得方法，通過交換元素，保證根元素比孩子元素大。
??? 第1趟，堆頂元素array[0]與array[n-1]交換，保證array[n-1]的數(shù)值正確，根據(jù)array[0]新的數(shù)值更新堆。
??? 第2趟，堆頂元素array[0]與array[n-2]交換，保證array[n-2]的數(shù)值正確，根據(jù)array[0]新的數(shù)值更新堆。
??? ···

??? 第n-1趟，堆頂元素array[0]與array[1]交換，保證array[1]的數(shù)值正確，根據(jù)array[0]新的數(shù)值更新堆。

2. 復(fù)雜度

??? 平均時(shí)間復(fù)雜度為O(N*logN)，空間復(fù)雜度為O(1)。

3. 代碼???

void?make_heap(int?array[],?int?n,?int?node)?{?//?自底向上，構(gòu)建堆
??int?left?=?2?*?node + 1;
??int?right?=?2?*?node?+?2;
??if(left?>?n-1)?return;
??else?if(right?>?n-1)?{?//?堆是完全的二叉樹，所以此時(shí)不需要遞歸
????if(array[node]?<?array[left])?{
??????swap(array[node],?array[left]);
????}
??}
??else?{
????make_heap(array,?n,?left);
????make_heap(array,?n,?right);
????if(array[node]?<?array[left]?&&?array[right]?<=?array[left])?{
??????swap(array[node],?array[left]);
????}
????else?if(array[node]?<?array[right]?&&?array[left]?<=?array[right])?{
??????swap(array[node],?array[right]);
????}
??}
}
void?update_heap(int?array[],?int?n,?int?node)?{?//?自頂向下，更新堆
??int?left?=?2?*?n?+ 1;
??int?right?=?2?*?n?+?2;
??if(left?>?n-1)?return;
??else?if(right?>?n-1)?{
????if(array[node]?<?array[left])?
??????swap(array[node],?array[left]);
??}
??else?{
????if(array[node]?<?array[left]?&&?array[right]?<=?array[left])?{
??????swap(array[node],?array[left]);
??????update_heap(array,?n,?left);
????}
????else?if(array[node]?<?array[right]?&&?array[left]?<=?array[right])?{
??????swap(array[node],?array[right]);
??????update_heap(array,?n,?right);
????}
??}
}
void?heap_sort(int?array[],?int?n)?{
??make_heap(array,?n,?0);
??for(int?i=n;?i>=1;?i--)?{
????swap(array[i],?array[0]);
????update_heap(array,?n,?node);
??}?
}

??? 實(shí)際上，堆的構(gòu)建和更新都可以使用非遞歸的方式實(shí)現(xiàn)，對(duì)于堆的構(gòu)建，需要首先找到最后一個(gè)有孩子的節(jié)點(diǎn)array[k]，然后從array[k]一直更新到array[0]即可，其中的k=n/2。k的求法如下：假設(shè)k存在，2*k+1=n或者2*k+2=n，對(duì)于第一種情況，k==n/2，對(duì)于第二種情況，k==n/2-1。對(duì)于堆的更新，就更簡單了，只要從array[0]開始，選擇一條通路，一直向下更新，直到?jīng)]有孩子了為止。
?? 值得注意的是，對(duì)于下標(biāo)從0開始的數(shù)組，k號(hào)節(jié)點(diǎn)的孩子節(jié)點(diǎn)分別是2*k+1和2*k+2。?而對(duì)于下標(biāo)從1開始得數(shù)組，k號(hào)節(jié)點(diǎn)的孩子節(jié)點(diǎn)分別是2*k和2*k+1。
??? 堆排序?qū)儆谶x擇排序，實(shí)際上就是利用最大堆這個(gè)數(shù)據(jù)結(jié)構(gòu)，每次選擇一個(gè)剩余元素中最大的元素，交換到合適的位置上去。

4. 參考資料

??? 維基百科-堆排序??? http://en.wikipedia.org/wiki/Heapsort

總結(jié)

以上是生活随笔為你收集整理的算法熟记-排序系列-堆排序的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。