9.7.2?堆排序算法

??????? 堆排序（Heap Sort）就是利用堆（假設利用大頂堆）進行排序的方法。它的基本思想是，將待排序的序列構造成一個大頂堆。此時，整個序列的最大值就是堆頂的根結點。將它移走（其實就是將其與堆數組的末尾元素交換，此時末尾元素就是最大值），然后將剩余的n-1個序列重新構造成一個堆，這樣就會得到n個元素中的次小值。如此反復執行，便能得到一個有序序列了。
??

??????? 例如圖9-7-4，左圖是一個大頂堆，90為最大值，將90與20（末尾元素）互換，如中圖所示，此時90就成了整個堆序列的最后一個元素，將20經過調整，使得除90以外的結點繼續滿足大頂堆定義（所有結點都大于等于其子孩子），見右圖。然后再考慮將30與80互換……
??????? 相信大家有些明白堆排序的基本思想了，不過要實現它還需要解決兩個問題：（1）如何由一個無序序列構建成一個堆？（2）如果在輸出堆頂元素后，調整剩余元素成為一個新的堆？要解釋清楚它們，讓我們來看代碼。

?

/* 對順序表L進行堆排序 */ void HeapSort(SqList *L) {int i;for(i=L->length/2;i>0;i--) /* 把L中的r構建成一個大頂堆 */HeapAdjust(L,i,L->length);for(i=L->length;i>1;i--){ swap(L,1,i); /*將堆頂記錄和當前未經排序子序列的最后一個記錄交換*/HeapAdjust(L,1,i-1); /* 將L->r[1..i-1]重新調整為大頂堆 */} }

??????? 從代碼中也可以看出，整個排序過程分為兩個for循環。第一個循環要完成的就是將現在的待排序序列構建成一個大頂堆。第二個循環要完成的就是逐步將每個最大值的根結點與末尾元素交換，并且再調整其成為大頂堆。
??????? 假設我們要排序的序列是{50,10,90,30,70,40,80,60,20} ，那么L.length=9，第一個for循環，代碼第4行，i是從?9/2?=4開始，4→3→2→1的變量變化。為什么不是從1到9，或者從9到1，而是從4到1呢？其實我們看了圖9-7-5就明白了，它們都有什么規律？它們都是有孩子的結點。注意灰色結點的下標編號就是1、2、3、4。

?
??????? 我們所謂的將待排序的序列構建成為一個大頂堆，其實就是從下往上，從右到左，將每個非終端結點（非葉結點）當作根結點，將其和其子樹調整成大頂堆。i的4→3→2→1的變量變化，其實也就是30，90，10、50的結點調整過程。
??????? 既然已經弄清楚i的變化是在調整哪些元素了，現在我們來看關鍵的HeapAdjust（堆調整）函數是如何實現的。

?

/* 已知L->r[s..m]中記錄的關鍵字除L->r[s]之外均滿足堆的定義， *//* 本函數調整L->r[s]的關鍵字,使L->r[s..m]成為一個大頂堆 */ void HeapAdjust(SqList *L,int s,int m) { int temp,j;temp=L->r[s];for(j=2*s;j<=m;j*=2) /* 沿關鍵字較大的孩子結點向下篩選 */{if(j<m && L->r[j]<L->r[j+1])++j; /* j為關鍵字中較大的記錄的下標 */if(temp>=L->r[j])break; /* rc應插入在位置s上 */L->r[s]=L->r[j];s=j;}L->r[s]=temp; /* 插入 */ }

1)?函數被第一次調用時，s=4，m=9，傳入的SqList參數的值為length=9,r[10]={0,50,10,90, 30,70,40,80,60,20}
2)?第4行，將L.r[s]=L.r[4]=30賦值給temp。如圖9-7-6

3)?第5～13行，循環遍歷其結點的孩子。這里j變量為什么是從2*s開始呢？又為什么是j*=2遞增呢？原因還是二叉樹的性質5，因為我們這棵是完全二叉樹，當前結點序號是s，其左孩子的序號一定是2s，右孩子的序號一定是2s+1，它們的孩子當然也是以2的位數序號增加，因此j變量才是這樣循環。
4)?第7～8行，此時j=2*4=8， j<m說明它不是最后一個結點，如果L.r[j]<L.r[j+1]，則說明左孩子小于右孩子。我們的目的是要找到較大值，當然需要讓j+1以便變成指向右孩子的下標。當前30的左右孩子是60和20，并不滿足此條件，因此j還是8。
5)?第9～10行，temp=30，L.r[j]=60，并不滿足條件。
6)?第11～12行，將60賦值給L.r[4]，并令s=j=8。也就是說，當前算出，以30為根結點的子二叉樹，當前最大值是60，在第8的位置。注意此時L.r[4]和L.r[8]的值均為60。
7)?再循環因為j=2*j=16，m=9，j>m，因此跳出循環
8)?第14行，將temp=30賦值給L.r[s]=L.r[8]，完成30與60的交換工作。如圖9-7-7。本次函數調用完成。

?

9)?再次調用HeapAdjust，此時s=3，m=9。第4行，temp=L.r[3]=90，第7～8行，由于40<80得到j+1=2*s+1=7。9～10行，由于90>80，因此退出循環，最終本次調用，整個序列未發什么改變。
10)?再次調用HeapAdjust，此時s=2，m=9。第4行，temp=L.r[2]=10，第7～8行，60<70，使得j=5。最終本次調用使得10與70進行了互換。

11)?再次調用HeapAdjust，此時s=1，m=9。第4行，temp=L.r[1]=50，第7～8行，70<90，使得j=3。第11～12行，L.r[1]被賦值了90，并且s=3，再循環，由于2j=6并未大于m，因此再次執行循環體，使得L.r[3]被賦值了80，完成循環后，L.[7]被賦值為50，最終本次調用使得50、90、80進行了輪換。
?

??????? 到此為止，我們構建大頂堆的過程算是完成了，也就是HeapSort函數的第4～5行循環執行完畢。或許是有點復雜，如果不明白，多試著模擬計算機執行的方式走幾遍，應該就可以理解其原理。
??????? 接下來HeapSort函數的第6～11行就是正式的排序過程，由于有了前面的充分準備，其實這個排序就比較輕松了。下面是這部分代碼。

?

6 for(i=L->length;i>1;i--) 7 { 8 swap(L,1,i); /* 將堆頂記錄和當前未經排序子序列的最后一個記錄交換 */ 9 HeapAdjust(L,1,i-1); /* 將L->r[1..i-1]重新調整為大頂堆 */ 10 }

1)?當i=9時，第8行，交換20與90，第9行，將當前的根結點20進行大頂堆的調整，調整過程和剛才流程一樣，找到它左右子結點的較大值，互換，再找到其子結點的較大值互換。此時序列變為{80,70,50,60,10,40,20,30,90}，如圖9-7-10
?

2)?當i=8時，交換30與80，并將30與70交換，再與60交換，此時序列變為{70,60,50,30,10,40,20,80,90}，如圖9-7-10
?

3)?后面的變化完全類似，不解釋，只看圖。
?

??????? 最終就得到一個完全有序的序列了。

?

9.7.3?堆排序復雜度分析
??????? 堆排序的效率到底有多好呢？我們來分析一下。
??????? 它的運行時間主要是消耗在初始構建堆和在重建堆時的反復篩選上。
??????? 在構建堆的過程中，因為我們是完全二叉樹從最下層最右邊的非終端結點開始構建，將它與其孩子進行比較和若有必要的互換，對于每個非終端結點來說，其實最多進行兩次比較和互換操作，因此整個構建堆的時間復雜度為O(n)。
??????? 在正式排序時，第i次取堆頂記錄重建堆需要用O(logi)的時間（完全二叉樹的某個結點到根結點的距離為?log2i?+1），并且需要取n-1次堆頂記錄，因此，重建堆的時間復雜度為O(nlogn)。
??????? 所以總體來說，堆排序的時間復雜度為O(nlogn)。由于堆排序對原始記錄的排序狀態并不敏感，因此它無論是最好、最壞和平均時間復雜度均為O(nlogn)。這在性能上顯然要遠遠好過于冒泡、簡單選擇、直接插入的O(n²)的時間復雜度了。?
??????? 空間復雜度上，它只有一個用來交換的暫存單元，也算是非常的不錯。不過由于記錄的比較與交換是跳躍式進行，因此堆排序也是一種不穩定的排序方法。
??????? 另外，由于初始構建堆所需的比較次數較多，因此，它并不適合待排序序列個數較少的情況。?

出處：http://write.blog.csdn.net/postedit

總結

以上是生活随笔為你收集整理的《大话数据结构》第9章 排序 9.7 堆排序（下）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。