軟考軟件設計師專題講義十：常用的算法設計方法

　　2.幾個重要的算法程序

　　2.1 堆排序

　　堆排序也是選擇排序的一種，其特點是，在以后各趟的“選擇”中利用在第一趟選擇中已經得到的關鍵字比較的結果。

　　堆的定義: 堆是滿足下列性質的數列{r1, r2, …，rn}： 或 若將此數列看成是一棵完全二叉樹，則堆或是空樹或是滿足下列特性的完全二叉樹：其左、右子樹分別是堆，并且當左/右子樹不空時，根結點的值小于(或大于)左/右子樹根結點的值。

　　由此，若上述數列是堆，則r1必是數列中的最小值或最大值，分別稱作小頂堆或大頂堆。

　　堆排序即是利用堆的特性對記錄序列進行排序的一種排序方法。具體作法是：先建一個“大頂堆”，即先選得一個關鍵字為最大的記錄，然后與序列中最后一個記錄交換，之后繼續(xù)對序列中前n-1記錄進行“篩選”，重新將它調整為一個“大頂堆”，再將堆頂記錄和第n-1個記錄交換，如此反復直至排序結束。

　　所謂“篩選”指的是，對一棵左/右子樹均為堆的完全二叉樹，“調整”根結點使整個二叉樹為堆。

　　堆排序的算法如下所示：

　　template

　　void HeapSort ( Elem R[], int n ) {

　　// 對記錄序列R[1..n]進行堆排序。

　　for ( i=n/2; i>0; --i )

　　// 把R[1..n]建成大頂堆

　　HeapAdjust ( R, i, n );

　　for ( i=n; i>1; --i ) {

　　R[1]←→R;

　　// 將堆頂記錄和當前未經排序子序列

　　// R[1..i]中最后一個記錄相互交換

　　HeapAdjust(R, 1, i-1);

　　// 將R[1..i-1] 重新調整為大頂堆

　　}

　　} // HeapSort

　　其中篩選的算法如下所示。為將R[s..m]調整為“大頂堆”，算法中“篩選”應沿關鍵字較大的孩子結點向下進行。

　　Template

　　void HeapAdjust (Elem R[], int s, int m) {

　　// 已知R[s..m]中記錄的關鍵字除R[s].key之

　　// 外均滿足堆的定義，本函數調整R[s] 的關

　　// 鍵字，使R[s..m]成為一個大頂堆(對其中

　　// 記錄的關鍵字而言)

　　rc = R[s];

　　for ( j=2*s; j<=m; j*=2 ) {// 沿key較大的孩子結點向下篩選

　　if ( j if ( rc.key >= R[j].key ) break; // rc應插入在位置s上

　　R[s] = R[j]; s = j;

　　}

　　R[s] = rc; // 插入

　　} // HeapAdjust

　　堆排序的時間復雜度分析：

　　1. 對深度為k的堆，“篩選”所需進行的關鍵字比較的次數至多為2(k-1);

　　2.對n個關鍵字，建成深度為+1)ûlog2nëh(=的堆，所需進行的關鍵字比較的次數至多為4n;

　　3. 調整“堆頂”n-1次，總共進行的關鍵字比較的次數不超過

　　+û2(log2(n-1) + …+log22)ûlog2(n-2)ë

　　因此，堆排序的時間復雜度為O(nlogn)

　　　　　　　計算機軟考軟件設計師練習試題及答案解析匯總