軟考軟件設計師專題講義九：數(shù)據(jù)結構相關算法

　　堆排序：對n個元素的序列進行堆排序，先將其建成堆，以根結點與第n個結點交換;調整前n-1個結點成為堆，再以根結點與第n-1個結點交換;重復上述操作，直到整個序列有序。

　　【算法10.10】

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

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

　　rc=h->r[s];

　　for(j=2*s;j<=m;j=j*2) /* 沿關鍵碼較大的子女結點向下篩選 */

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

　　j=j+1; /* 為關鍵碼較大的元素下標*/

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

　　h->r[s]=h->r[j]; s=j; /* 使s結點滿足堆定義 */

　　}

　　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]重新調整為堆*/

　　}

　　}

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

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

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

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