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

　　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);

　　}

　　}

　　另外，外排序是對(duì)大型文件的排序，待排序的記錄存儲(chǔ)在外存中，在排序過(guò)程中，內(nèi)存只存儲(chǔ)文件的一部分記錄，整個(gè)排序過(guò)程需進(jìn)行多次的內(nèi)外存間的交換。

　　直接插入排序算法分析：

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

　　先來(lái)看看向有序表中插入一個(gè)記錄的方法：

　　設(shè)1

　　【算法10.1】

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

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

　�、� 若r[0].key≥r[i].key，轉(zhuǎn)④。 //插入位置確定

　�、� 若r[0].key < r[i].key時(shí)，

　　r[i+1]=r[i];i=i-1;轉(zhuǎn)②。 //調(diào)整待插入位置

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

　　直接插入排序方法：僅有一個(gè)記錄的表總是有序的，因此，對(duì)n個(gè)記錄的表，可從第二個(gè)記錄開始直到第n個(gè)記錄，逐個(gè)向有序表中進(jìn)行插入操作，從而得到n個(gè)記錄按關(guā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) /*小于時(shí)，需將elem[i]插入有序表*/

　　{ p->elem[0].key=p->elem[i].key; /*為統(tǒng)一算法設(shè)置監(jiān)測(cè)*/

　　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; /*插入到正確位置*/

　　}

　　}

　　【效率分析】

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

　　時(shí)間效率：向有序表中逐個(gè)插入記錄的操作，進(jìn)行了n-1趟，每趟操作分為比較關(guān)鍵碼和移動(dòng)記錄，而比較的次數(shù)和移動(dòng)記錄的次數(shù)取決于待排序列按關(guān)鍵碼的初始排列。

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

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

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

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

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

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

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