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

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

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

　　① i=1; //設置從第一個記錄開始進行兩兩比較

　　② 若i≥j，一趟冒泡結束。

　　③ 比較r[i].key與r[i+1].key，若r[i].key≤r[i+1].key，不交換，轉⑤

　　④ 當r[i].key>r[i+1].key時， r[0]=r[i];r[i]=r[i+1];r[i+1]=r[0];

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

　　⑤ i=i+1; 調整對下兩個記錄進行兩兩比較，轉②

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

　　【算法10.6】

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

　　② 若j<2，排序結束

　　③ i=1; //一趟冒泡，設置從第一個記錄開始進行兩兩比較，

　　④ 若i≥j，一趟冒泡結束，j=j-1;冒泡表的記錄數-1，轉②

　　⑤ 比較r[i].key與r[i+1].key，若r[i].key≤r[i+1].key，不交換，轉⑤

　　⑥ 當r[i].key>r[i+1].key時， r[i]<-->r[i+1]; 將r[i]與r[i+1]交換

　　⑦ i=i+1; 調整對下兩個記錄進行兩兩比較，轉④

　　【效率分析】

　　空間效率：僅用了一個輔助單元。

　　時間效率：總共要進行n-1趟冒泡，對j個記錄的表進行一趟冒泡需要j-1次關鍵碼比較。

　　移動次數：

　　最好情況下：待排序列已有序，不需移動。

　　快速排序：

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

　　【算法10.8】

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

　　{ /*對順序表tbl中的子序列tbl->[low…high]作快排序*/

　　if(low

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

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

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

　　}

　　}

　　【效率分析】

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

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