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

　　冒泡排序(Bubble Sort)算法分析：

　　先來看看待排序列一趟冒泡的過程：設(shè)1

　　通過兩兩比較、交換，重新安排存放順序，使得r[j]是序列中關(guān)鍵碼最大的記錄。一趟冒泡方法為：

　�、� i=1; //設(shè)置從第一個(gè)記錄開始進(jìn)行兩兩比較

　�、� 若i≥j，一趟冒泡結(jié)束。

　�、� 比較r[i].key與r[i+1].key，若r[i].key≤r[i+1].key，不交換，轉(zhuǎn)⑤

　�、� 當(dāng)r[i].key>r[i+1].key時(shí)， r[0]=r[i];r[i]=r[i+1];r[i+1]=r[0];

　　將r[i]與r[i+1]交換

　�、� i=i+1; 調(diào)整對下兩個(gè)記錄進(jìn)行兩兩比較，轉(zhuǎn)②

　　冒泡排序方法：對n個(gè)記錄的表，第一趟冒泡得到一個(gè)關(guān)鍵碼最大的記錄r[n]，第二趟冒泡對n-1個(gè)記錄的表，再得到一個(gè)關(guān)鍵碼最大的記錄r[n-1]，如此重復(fù)，直到n個(gè)記錄按關(guān)鍵碼有序的表。

　　【算法10.6】

　　① j=n; //從n記錄的表開始

　�、� 若j<2，排序結(jié)束

　　③ i=1; //一趟冒泡，設(shè)置從第一個(gè)記錄開始進(jìn)行兩兩比較，

　�、� 若i≥j，一趟冒泡結(jié)束，j=j-1;冒泡表的記錄數(shù)-1，轉(zhuǎn)②

　�、� 比較r[i].key與r[i+1].key，若r[i].key≤r[i+1].key，不交換，轉(zhuǎn)⑤

　　⑥ 當(dāng)r[i].key>r[i+1].key時(shí)， r[i]<-->r[i+1]; 將r[i]與r[i+1]交換

　�、� i=i+1; 調(diào)整對下兩個(gè)記錄進(jìn)行兩兩比較，轉(zhuǎn)④

　　【效率分析】

　　空間效率：僅用了一個(gè)輔助單元。

　　時(shí)間效率：總共要進(jìn)行n-1趟冒泡，對j個(gè)記錄的表進(jìn)行一趟冒泡需要j-1次關(guān)鍵碼比較。

　　移動(dòng)次數(shù)：

　　最好情況下：待排序列已有序，不需移動(dòng)。

　　快速排序：

　　快速排序是通過比較關(guān)鍵碼、交換記錄，以某個(gè)記錄為界(該記錄稱為支點(diǎn))，將待排序列分成兩部分。其中，一部分所有記錄的關(guān)鍵碼大于等于支點(diǎn)記錄的關(guān)鍵碼，另一部分所有記錄的關(guān)鍵碼小于支點(diǎn)記錄的關(guān)鍵碼。我們將待排序列按關(guān)鍵碼以支點(diǎn)記錄分成兩部分的過程，稱為一次劃分。對各部分不斷劃分，直到整個(gè)序列按關(guān)鍵碼有序。

　　【算法10.8】

　　void QSort(S_TBL *tbl,int low,int high) /*遞歸形式的快排序*/

　　{ /*對順序表tbl中的子序列tbl->[low…h(huán)igh]作快排序*/

　　if(low

　　{ pivotloc=partition(tbl,low,high); /*將表一分為二*/

　　QSort(tbl,low,pivotloc-1); /*對低子表遞歸排序*/

　　QSort(tbl,pivotloc+1,high); /*對高子表遞歸排序*/

　　}

　　}

　　【效率分析】

　　空間效率：快速排序是遞歸的，每層遞歸調(diào)用時(shí)的指針和參數(shù)均要用棧來存放，遞歸調(diào)用層次數(shù)與上述二叉樹的深度一致。因而，存儲開銷在理想情況下為O(log2n)，即樹的高度;在最壞情況下，即二叉樹是一個(gè)單鏈，為O(n)。

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