軟考軟件設(shè)計(jì)師專(zhuān)題講義九：數(shù)據(jù)結(jié)構(gòu)相關(guān)算法

　　堆排序：對(duì)n個(gè)元素的序列進(jìn)行堆排序，先將其建成堆，以根結(jié)點(diǎn)與第n個(gè)結(jié)點(diǎn)交換;調(diào)整前n-1個(gè)結(jié)點(diǎn)成為堆，再以根結(jié)點(diǎn)與第n-1個(gè)結(jié)點(diǎn)交換;重復(fù)上述操作，直到整個(gè)序列有序。

　　【算法10.10】

　　void HeapAdjust(S_TBL *h，int s，int m)

　　{/*r[s…m]中的記錄關(guān)鍵碼除r[s]外均滿(mǎn)足堆的定義，本函數(shù)將對(duì)第s個(gè)結(jié)點(diǎn)為根的子樹(shù)篩選，使其成為大頂堆*/

　　rc=h->r[s];

　　for(j=2*s;j<=m;j=j*2) /* 沿關(guān)鍵碼較大的子女結(jié)點(diǎn)向下篩選 */

　　{ if(jr[j].keyr[j+1].key)

　　j=j+1; /* 為關(guān)鍵碼較大的元素下標(biāo)*/

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

　　h->r[s]=h->r[j]; s=j; /* 使s結(jié)點(diǎn)滿(mǎn)足堆定義 */

　　}

　　h->r[s]=rc; /* 插入 */

　　}

　　void HeapSort(S_TBL *h)

　　{ for(i=h->length/2;i>0;i--) /* 將r[1..length]建成堆 */

　　HeapAdjust(h，i，h->length);

　　for(i=h->length;i>1;i--)

　　{ h->r[1]<-->h->r[i]; /* 堆頂與堆低元素交換 */

　　HeapAdjust(h，1，i-1); /*將r[1..i-1]重新調(diào)整為堆*/

　　}

　　}

　　交換記錄至多k次。所以，在建好堆后，排序過(guò)程中的篩選次數(shù)不超過(guò)下式：

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

　　而建堆時(shí)的比較次數(shù)不超過(guò)4n次，因此堆排序最壞情況下，時(shí)間復(fù)雜度也為O(nlog2n)。

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