u 快速排序

　　void r_quick(int e[], int low, int high)

　　{ int i, j, t;

　　if(low

　　i=low; j=high; t=e[low];

　　while(i

　　while (it) j--;

　　if(i

　　while (i

　　if(I

　　}

　　e[i]=t;

　　r_quick(e,low,i-1);

　　r_quick(w,i+1,high);

　　}

　　}

　　另外，外排序是對大型文件的排序，待排序的記錄存儲在外存中，在排序過程中，內存只存儲文件的一部分記錄，整個排序過程需進行多次的內外存間的交換。

　　直接插入排序算法分析：

　　設有n個記錄，存放在數組r中，重新安排記錄在數組中的存放順序，使得按關鍵碼有序。即r[1].key≤r[2].key≤……≤r[n].key

　　先來看看向有序表中插入一個記錄的方法：

　　設1

　　【算法10.1】

　　① r[0]=r[j]; //r[j]送r[0]中，使r[j]為待插入記錄空位

　　i=j-1; //從第i個記錄向前測試插入位置，用r[0]為輔助單元， 可免去測試i<1。

　　② 若r[0].key≥r[i].key，轉④。 //插入位置確定

　　③ 若r[0].key < r[i].key時，

　　r[i+1]=r[i];i=i-1;轉②。 //調整待插入位置

　　④ r[i+1]=r[0];結束。 //存放待插入記錄

　　直接插入排序方法：僅有一個記錄的表總是有序的，因此，對n個記錄的表，可從第二個記錄開始直到第n個記錄，逐個向有序表中進行插入操作，從而得到n個記錄按關鍵碼有序的表。

　　【算法10.2】

　　void InsertSort(S_TBL &p)

　　{ for(i=2;i<=p->length;i++)

　　if(p->elem[i].key < p->elem[i-1].key) /*小于時，需將elem[i]插入有序表*/

　　{ p->elem[0].key=p->elem[i].key; /*為統一算法設置監測*/

　　for(j=i-1;p->elem[0].key < p->elem[j].key;j--)

　　p->elem[j+1].key=p->elem[j].key; /*記錄后移*/

　　p->elem[j+1].key=p->elem[0].key; /*插入到正確位置*/

　　}

　　}

　　【效率分析】

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

　　時間效率：向有序表中逐個插入記錄的操作，進行了n-1趟，每趟操作分為比較關鍵碼和移動記錄，而比較的次數和移動記錄的次數取決于待排序列按關鍵碼的初始排列。

　　最好情況下：即待排序列已按關鍵碼有序，每趟操作只需1次比較2次移動。

　　總比較次數=n-1次

　　總移動次數=2(n-1)次

　　最壞情況下：即第j趟操作，插入記錄需要同前面的j個記錄進行j次關鍵碼比較，移動記錄的次數為j+2次。

　　平均情況下：即第j趟操作，插入記錄大約同前面的j/2個記錄進行關鍵碼比較，移動記錄的次數為j/2+2次。

　　由此，直接插入排序的時間復雜度為O(n2)。是一個穩定的排序方法。

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