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

　　時間效率：在n個記錄的待排序列中，一次劃分需要約n次關(guān)鍵碼比較，時效為O(n)，若設(shè)T(n)為對n個記錄的待排序列進(jìn)行快速排序所需時間。

　　理想情況下：每次劃分，正好將分成兩個等長的子序列，則

　　T(n)≤cn+2T(n/2) c是一個常數(shù)

　　≤cn+2(cn/2+2T(n/4))=2cn+4T(n/4)

　　≤2cn+4(cn/4+T(n/8))=3cn+8T(n/8)

　　······

　　≤cnlog2n+nT(1)=O(nlog2n)

　　最壞情況下：即每次劃分，只得到一個子序列，時效為O(n2)。

　　快速排序是通常被認(rèn)為在同數(shù)量級(O(nlog2n))的排序方法中平均性能最好的。但若初始序列按關(guān)鍵碼有序或基本有序時，快排序反而蛻化為冒泡排序。為改進(jìn)之，通常以“三者取中法”來選取支點(diǎn)記錄，即將排序區(qū)間的兩個端點(diǎn)與中點(diǎn)三個記錄關(guān)鍵碼居中的調(diào)整為支點(diǎn)記錄�？焖倥判蚴且粋�不穩(wěn)定的排序方法。

　　選擇排序

　　選擇排序主要是每一趟從待排序列中選取一個關(guān)鍵碼最小的記錄，也即第一趟從n個記錄中選取關(guān)鍵碼最小的記錄，第二趟從剩下的n-1個記錄中選取關(guān)鍵碼最小的記錄，直到整個序列的記錄選完。這樣，由選取記錄的順序，便得到按關(guān)鍵碼有序的序列。

　　簡單選擇排序：

　　操作方法：第一趟，從n個記錄中找出關(guān)鍵碼最小的記錄與第一個記錄交換;第二趟，從第二個記錄開始的n-1個記錄中再選出關(guān)鍵碼最小的記錄與第二個記錄交換;如此，第i趟，則從第i個記錄開始的n-i+1個記錄中選出關(guān)鍵碼最小的記錄與第i個記錄交換，直到整個序列按關(guān)鍵碼有序。

　　【算法10.9】

　　void SelectSort(S_TBL *s)

　　{ for(i=1;ilength;i++)

　　{ /* 作length-1趟選取 */

　　for(j=i+1，t=i;j<=s->length;j++)

　　{ /* 在i開始的length-n+1個記錄中選關(guān)鍵碼最小的記錄 */

　　if(s->elem[t].key>s->elem[j].key)

　　t=j; /* t中存放關(guān)鍵碼最小記錄的下標(biāo) */

　　}

　　s->elem[t]<-->s->elem[i]; /* 關(guān)鍵碼最小的記錄與第i個記錄交換 */

　　}

　　}

　　從程序中可看出，簡單選擇排序移動記錄的次數(shù)較少，但關(guān)鍵碼的比較次數(shù)依然是

　　堆排序(Heap Sort)：設(shè)有n個元素的序列 k1，k2，…，kn，當(dāng)且僅當(dāng)滿足下述關(guān)系之一時，稱之為堆。

　　若以一維數(shù)組存儲一個堆，則堆對應(yīng)一棵完全二叉樹，且所有非葉結(jié)點(diǎn)的值均不大于(或不小于)其子女的值，根結(jié)點(diǎn)的值是最小(或最大)的。

　　設(shè)有n個元素，將其按關(guān)鍵碼排序。首先將這n個元素按關(guān)鍵碼建成堆，將堆頂元素輸出，得到n個元素中關(guān)鍵碼最小(或最大)的元素。然后，再對剩下的n-1個元素建成堆，輸出堆頂元素，得到n個元素中關(guān)鍵碼次小(或次大)的元素。如此反復(fù)，便得到一個按關(guān)鍵碼有序的序列。稱這個過程為堆排序。

　　因此，實(shí)現(xiàn)堆排序需解決兩個問題：

　　1. 如何將n個元素的序列按關(guān)鍵碼建成堆;

　　2. 輸出堆頂元素后，怎樣調(diào)整剩余n-1個元素，使其按關(guān)鍵碼成為一個新堆。

　　首先，討論輸出堆頂元素后，對剩余元素重新建成堆的調(diào)整過程。

　　調(diào)整方法：設(shè)有m個元素的堆，輸出堆頂元素后，剩下m-1個元素。將堆底元素送入堆頂，堆被破壞，其原因僅是根結(jié)點(diǎn)不滿足堆的性質(zhì)。將根結(jié)點(diǎn)與左、右子女中較小(或小大)的進(jìn)行交換。若與左子女交換，則左子樹堆被破壞，且僅左子樹的根結(jié)點(diǎn)不滿足堆的性質(zhì);若與右子女交換，則右子樹堆被破壞，且僅右子樹的根結(jié)點(diǎn)不滿足堆的性質(zhì)。繼續(xù)對不滿足堆性質(zhì)的子樹進(jìn)行上述交換操作，直到葉子結(jié)點(diǎn)，堆被建成。稱這個自根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的調(diào)整過程為篩選。

　　再討論對n個元素初始建堆的過程。

　　建堆方法：對初始序列建堆的過程，就是一個反復(fù)進(jìn)行篩選的過程。n個結(jié)點(diǎn)的完全

　　子樹成為堆，之后向前依次對各結(jié)點(diǎn)為根的子樹進(jìn)行篩選，使之成為堆，直到根結(jié)點(diǎn)。

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