C++實現堆排序

C++實現堆排序

堆排序是一種具有合並排序和插入排序共同優點的排序方法。它的時間復雜度為O(nlgn)，它也是一種原地排序算法：在任何時候，數組中只有常數個元素存儲在輸入數組以外。要介紹堆排序首先要介紹什麼是堆。

1.建堆：堆數據結構是一種數組對象，它可以被視為一顆完全二叉樹，如下圖。右邊數組表示的堆可以用左邊的完全二叉樹來表示，其中若父節點對應數組下標為i，則其左孩子對應數組下標為2*i，右孩子為2*i+1。

具體代碼如下：<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+dm9pZCBidWlsZE1heEhlYXAoaW50IGFbXSAsIGludCBoZWFwU2l6ZSl7PGJyPgpmb3IoaW50IGkgPSBoZWFwU2l6ZS8yO2kgPj0gMTstLWkpPGJyPgptYXhfaGVhcGlmeShhLGksaGVhcFNpemUpOyAvL7G+0NC0+sLrtffTw21heF9oZWFwaWZ5uq/K/cC0saOz1tfutPO20dDU1sqjrL3Tz8LAtLvhvenJ3LW9oaNoZWFwU2l6Zc6qttG089ChoaM8YnI+Cn08L3A+CjxwPjIusaOz1rj5ttHQ1NbKo7q908/CwLS96cnctPO4+bbR0+vQobj5ttG1xMf4sfCho7TzuPm20cSzuPa92rXjtcQmIzIwNTQwO9futuDKx7rNxuS4uL3atePSu9H5tPOho9ChuPm20bXE1+nWr7jVusPP4Le0oaPU2rbRxcXQ8tbQztLDx8q508O1xMrHtPO4+bbRoaPOqsHLsaOz1rTzuPm20bXE0NTWyqOsztLDx7zZyei008/CserOqmm1xMr91+nUqsvYv6rKvKOsvavG5CYjMjA1NDA70+vL/LXE1/O6otfTus3T0rqi19PP4LHIvc+jrNXSs/bX7rTzJiMyMDU0MDu21NOmtcTPwrHqbGFyZ2VzdKOsyOe5+2xhcmdlc3THobrD0+tpz+C1yKOs1PLLtcP3vdq142mxo7PWwcvX7rTzttHQ1NbKoaO38dTyvbu7u8/CserOqmxhcmdlc3S6zWnL+bbU06a1xMr91+nUqsvYJiMyMDU0MDujrLKix9K21M/CserOqmxhcmdlc3S1xNSqy9i8zND4vfjQ0KGwsaOz1rj5ttHQ1NbKobG1xLLZ1/eho9Xiw7TLtb/JxNzT0NCpzKvIsbemyfq2r9DUo6zEx8O00rvG8MC0v7S/tNXiuPa5/bPMsMmjujxpbWcgc3JjPQ=="" alt="\">

可以看到圖中節點值為4的節點的保持根堆性質過程。代碼如下：

void max_heapify(int a[],int i,int heapSize){
int lindex = 2*i,rindex = 2*i + 1,largest = 0;
if(lindex <= heapSize && a[lindex-1] > a[i-1])//判斷左孩子和節點i的值誰大，將大值得下標保存為largest
largest = lindex;
else
largest = i;

if(rindex <= heapSize && a[rindex-1] > a[largest-1])//判斷右孩子和節點largest的值誰大
largest = rindex;

if(largest != i){//如果largest不等於i
swap(a[i-1] , a[largest-1]);//交換
max_heapify(a,largest,heapSize);//繼續對下標為largest、大小為heapSize的節點進行“保持根堆性質”
}
}

以下是swap函數：

void swap(int& first , int& second){
int tem = 0;
tem = first;
first = second;
second = tem;
}

3.堆排序算法：我用一個圖來直觀表示吧！

過程大致是將大根堆的根節點與最後一個葉子節點交換，然後縮小數組范圍(即將heapSize減小)，將最大值排除掉，最後對新的根節點進行“保持堆性質方法”，依次類推，代碼如下：

void heapSort(int a[] , int heapSize){
buildMaxHeap(a , heapSize);//建堆
for(int i = heapSize;i >= 2;--i){
swap(a[0] , a[i-1]);//將根節點與最後的葉子節點交換
--heapSize;//縮小堆范圍
max_heapify(a,1,heapSize);//保持堆性質

}
}