軟考軟件設(shè)計(jì)師專(zhuān)題講義十：常用的算法設(shè)計(jì)方法

　　2.幾個(gè)重要的算法程序

　　2.1 堆排序

　　堆排序也是選擇排序的一種，其特點(diǎn)是，在以后各趟的“選擇”中利用在第一趟選擇中已經(jīng)得到的關(guān)鍵字比較的結(jié)果。

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

　　由此，若上述數(shù)列是堆，則r1必是數(shù)列中的最小值或最大值，分別稱(chēng)作小頂堆或大頂堆。

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

　　所謂“篩選”指的是，對(duì)一棵左/右子樹(shù)均為堆的完全二叉樹(shù)，“調(diào)整”根結(jié)點(diǎn)使整個(gè)二叉樹(shù)為堆。

　　堆排序的算法如下所示：

　　template

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

　　// 對(duì)記錄序列R[1..n]進(jìn)行堆排序。

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

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

　　HeapAdjust ( R, i, n );

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

　　R[1]←→R;

　　// 將堆頂記錄和當(dāng)前未經(jīng)排序子序列

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

　　HeapAdjust(R, 1, i-1);

　　// 將R[1..i-1] 重新調(diào)整為大頂堆

　　}

　　} // HeapSort

　　其中篩選的算法如下所示。為將R[s..m]調(diào)整為“大頂堆”，算法中“篩選”應(yīng)沿關(guān)鍵字較大的孩子結(jié)點(diǎn)向下進(jìn)行。

　　Template

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

　　// 已知R[s..m]中記錄的關(guān)鍵字除R[s].key之

　　// 外均滿(mǎn)足堆的定義，本函數(shù)調(diào)整R[s] 的關(guān)

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

　　// 記錄的關(guān)鍵字而言)

　　rc = R[s];

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

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

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

　　}

　　R[s] = rc; // 插入

　　} // HeapAdjust

　　堆排序的時(shí)間復(fù)雜度分析：

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

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

　　3. 調(diào)整“堆頂”n-1次，總共進(jìn)行的關(guān)鍵字比較的次數(shù)不超過(guò)

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

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

　　　　　　　計(jì)算機(jī)軟考軟件設(shè)計(jì)師練習(xí)試題及答案解析匯總