C語言排序中堆排序的技巧

堆是一個近似完全二叉樹的結(jié)構(gòu)，并同時滿足堆積的性質(zhì)：即子結(jié)點的鍵值或索引總是小于（或者大于）它的父節(jié)點。

對于堆的操作通常需要以下3個步驟：

最大堆調(diào)整（Max Heapify）：將堆的末端子節(jié)點作調(diào)整，使得子節(jié)點永遠小于父節(jié)點

創(chuàng)建最大堆（Build Max Heap）：將堆中的所有數(shù)據(jù)重新排序

堆排序（HeapSort）：移除位在第一個數(shù)據(jù)的根節(jié)點，并做最大堆調(diào)整的遞歸運算。

C代碼實現(xiàn)

代碼看起來比較抽象，將代碼運行時數(shù)據(jù)交換的過程打印出來，然后結(jié)合二叉樹的圖形來分析，就會比較好理解了。代碼運行過程中數(shù)據(jù)交換過程如下：

為了方便觀看這里使用二叉樹圖形生成軟件，通過二叉樹圖形來觀察數(shù)據(jù)交換過程。二叉樹圖形生成使用的是一個在線生成網(wǎng)站：mshang.ca/syntree 后面所有的二叉樹圖形都使用此軟件生成。

代碼一開始首先打印出原始數(shù)據(jù)

數(shù)組元素 0 8 1 5 4 3 7 9 2 6 將這10個數(shù)據(jù)在網(wǎng)站上使用公式生成二叉樹的圖表，軟件界面如下：

首先將數(shù)組從上至下按順序排列，轉(zhuǎn)換成二叉樹。

公式：0［8 ［5 9［2］］［4［6］］］ ［1［3］ ［7 ］］］

轉(zhuǎn)換成二叉樹之后，需要讓這個無序堆變成最大堆，也就是每個堆都實現(xiàn)父節(jié)點的值大于任何一個子節(jié)點值。從最后一個堆開始，依次比較父節(jié)點和子節(jié)點的值，如果子節(jié)點值大于父節(jié)點值，就需要交換。

創(chuàng)建最大堆： 6為最后一個子節(jié)點，所以從6開始依次和父節(jié)點比較，如果子節(jié)點大于父節(jié)點，就需要交換子節(jié)點和父節(jié)點的位置。從設(shè)備樹圖形中可以看出，子節(jié)點6大于父節(jié)點4，所以需要交換子節(jié)點的父節(jié)點的位置。

公式：0［8 ［5 9［2］］［6［4］］］ ［1［3］ ［7 ］］］

交換 6 和4

6交換完成后，接下來依次向前比較其他子節(jié)點，6前面的節(jié)點是2，2小于父節(jié)點5，繼續(xù)向前查找子節(jié)點9，子節(jié)點9大于父節(jié)點5，所以就交換9和5的位置。

公式：0［8 ［9 5［2］］［6［4］］］ ［1［3］ ［7 ］］］

交換9和5

接下來繼續(xù)向前查找，發(fā)現(xiàn)子節(jié)點7大于父節(jié)點1，繼續(xù)交換。

公式：0［8 ［9 5［2］］［6［4］］］ ［7［3］ ［1 ］］］

交換7和1

繼續(xù)向前查找發(fā)現(xiàn)子節(jié)點9大于父節(jié)點8，交換位置。

公式：0［9 ［8 5［2］］［6［4］］］ ［7［3］ ［1 ］］］

交換9和8

繼續(xù)比較其他節(jié)點

公式：9［0 ［8 5［2］］［6［4］］］ ［7［3］ ［1 ］］］

交換9和0

公式：9［8 ［0 5［2］］［6［4］］］ ［7［3］ ［1 ］］］

交換8和0

公式：9［8 ［5 0［2］］［6［4］］］ ［7［3］ ［1 ］］］

交換5和0

此時最大堆已經(jīng)創(chuàng)建完成，此時根節(jié)點的數(shù)字9就是數(shù)組中的最大值。

代碼中打印出來的數(shù)據(jù)順序和通過二叉樹圖形分析出來的順序完全一樣。此時最大堆調(diào)整已經(jīng)完成了。接下來就需要開始堆排序，依次將根節(jié)點的數(shù)據(jù)存放到最后一個節(jié)點，形成一個有序堆。

堆排序（最大堆調(diào)整）

首先交換數(shù)組中第一個元素，和排序好的前一個元素位置。此時數(shù)組中的第一個元素是9，排序完成之后最后一個元素是4，交換9和4.

公式：4［8 ［5 0［2］］［6［9］］］ ［7［3］ ［1 ］］］

交換9和4

交換完成后，此時最大值9所在的底部位置就成為了有序區(qū)，有序區(qū)之后就不會參與任何對比。接下來繼續(xù)調(diào)整父節(jié)點和子節(jié)點，確保父節(jié)點要大于子節(jié)點。

公式：8［4 ［5 0［2］］［6［9］］］ ［7［3］ ［1 ］］］

交換8和4

公式：8［6 ［5 0［2］］［4［9］］］ ［7［3］ ［1 ］］］

交換6和4

此時數(shù)字8稱為了根節(jié)點，是目前無序區(qū)中的最大值，將8和底部區(qū)的2交換，將當(dāng)前最大值8放到有序區(qū)中。

公式：2［6 ［5 0［8］］［4［9］］］ ［7［3］ ［1 ］］］

交換8和2

此時8已經(jīng)存放到了有序區(qū)中，此后就不參與任何交換了。此時2變?yōu)楦?jié)點后，需要在重新調(diào)整一次節(jié)點，確保父節(jié)點大于子節(jié)點。

公式：7［6 ［5 0［8］］［4［9］］］ ［2［3］ ［1 ］］］

交換7和2

公式：7［6 ［5 0［8］］［4［9］］］ ［3［2］ ［1 ］］］

交換3和2

此時數(shù)字7變?yōu)楦?jié)點，是無序區(qū)間的最大值。需要將根節(jié)點的數(shù)字移動到有序區(qū)中。

將根節(jié)點7和0交換位置。

公式：0［6 ［5 7［8］］［4［9］］］ ［3［2］ ［1 ］］］

交換7和0

接下來重新調(diào)整節(jié)點 公式：6［0 ［5 7［8］］［4［9］］］ ［3［2］ ［1 ］］］

交換6和0

公式：6［5 ［0 7［8］］［4［9］］］ ［3［2］ ［1 ］］］

交換5和0

此時6變?yōu)榱烁?jié)點，是無序區(qū)間的最大值。

將根節(jié)點和有序區(qū)間的前一個數(shù)字交換，也就是1和6需要交換。

公式：1［5 ［0 7［8］］［4［9］］］ ［3［2］ ［6 ］］］

交換6和1

接下來重新調(diào)節(jié)一次節(jié)點

公式：5［1 ［0 7［8］］［4［9］］］ ［3［2］ ［6 ］］］

交換5和1

公式：5［4 ［0 7［8］］［1［9］］］ ［3［2］ ［6 ］］］

交換4和1

此時5變成的根節(jié)點，需要將5移動到有序隊列中去。

接下來需要交換根節(jié)點5和無序節(jié)點2的位置

公式：2［4 ［0 7［8］］［1［9］］］ ［3［5］ ［6 ］］］

交換5和2

重新調(diào)整節(jié)點位置

公式：4［2 ［0 7［8］］［1［9］］］ ［3［5］ ［6 ］］］

交換4和2

此時4是無序列表中的最大值，需要交換4和1的位置

公式：1［2 ［0 7［8］］［4［9］］］ ［3［5］ ［6 ］］］

交換4和1

重新調(diào)整節(jié)點位置

公式：9［2 ［0 6［7］］［3［8］］］ ［1［4］ ［5 ］］］

交換3和1

此時3為無序列表中最大值，需要交換3和0的位置。

公式：0［2 ［3 7［8］］［4［9］］］ ［1［5］ ［6 ］］］

交換3和0

交換完成后重新調(diào)整節(jié)點位置 公式：9［0 ［2 6［7］］［3［8］］］ ［1［4］ ［5 ］］］

交換2和0

此時2變成了無序列表中最大值，1為有序列表的前一個值，交換2和1的位置。

公式：1［0 ［3 7［8］］［4［9］］］ ［2［5］ ［6 ］］］

交換2和1

此時1是根節(jié)點，無序列表中就剩0一個數(shù)字了，交換1和0。

公式：0［1 ［3 7［8］］［4［9］］］ ［2［5］ ［6 ］］］

交換1和0

這是0變成了根節(jié)點，而其他的所有數(shù)字都在有序列表中，無序列表中已經(jīng)沒有數(shù)字了，此時說明排序完成。

可以看出最好、最壞、一般情況下數(shù)據(jù)移動的次數(shù)和方法基本都差不多。

接下來隨機生成10000個數(shù)據(jù)，看看排序需要多長時間。

編輯：jq