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個記錄，存放在數(shù)組r中，重新安排記錄在數(shù)組中的存放順序，使得按關鍵碼有序。即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; /*為統(tǒng)一算法設置監(jiān)測*/

　　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趟，每趟操作分為比較關鍵碼和移動記錄，而比較的次數(shù)和移動記錄的次數(shù)取決于待排序列按關鍵碼的初始排列。

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

　　總比較次數(shù)=n-1次

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

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

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

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

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