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

　　兩路歸并的遞歸算法：

　　【算法10.13】

　　void MSort(ElemType *p，ElemType *p1，int s，int t)

　　{ /*將p[s…t]歸并排序?yàn)閜1[s…t]*/

　　if(s==t) p1[s]=p[s]

　　else

　　{ m=(s+t)/2; /*平分*p表*/

　　MSort(p，p2，s，m); /*遞歸地將p[s…m]歸并為有序的p2[s…m]*/

　　MSort(p，p2，m+1，t); /*遞歸地將p[m+1…t]歸并為有序的p2[m+1…t]*/

　　Merge(p2，p1，s，m+1，t); /*將p2[s…m]和p2[m+1…t]歸并到p1[s…t]*/

　　}

　　}

　　void MergeSort(S_TBL *p)

　　{ /*對(duì)順序表*p作歸并排序*/

　　MSort(p->elem，p->elem，1，p->length);

　　}

　　【效率分析】

　　需要一個(gè)與表等長(zhǎng)的輔助元素?cái)?shù)組空間，所以空間復(fù)雜度為O(n)。

　　對(duì)n個(gè)元素的表，將這n個(gè)元素看作葉結(jié)點(diǎn)，若將兩兩歸并生成的子表看作它們的父結(jié)點(diǎn)，則歸并過程對(duì)應(yīng)由葉向根生成一棵二叉樹的過程。所以歸并趟數(shù)約等于二叉樹的高度-1，即log2n，每趟歸并需移動(dòng)記錄n次，故時(shí)間復(fù)雜度為O(nlog2n)。

　　基數(shù)排序：

　　基數(shù)排序是一種借助于多關(guān)鍵碼排序的思想，是將單關(guān)鍵碼按基數(shù)分成“多關(guān)鍵碼”進(jìn)行排序的方法。

　　多關(guān)鍵碼排序：

　　設(shè)n個(gè)元素的待排序列包含d個(gè)關(guān)鍵碼{k1，k2，…，kd}，則稱序列對(duì)關(guān)鍵碼{k1，k2，…，kd}有序是指：對(duì)于序列中任兩個(gè)記錄r[i]和r[j](1≤i≤j≤n)都滿足下列有序關(guān)系：

　　其中k1稱為最主位關(guān)鍵碼，kd稱為最次位關(guān)鍵碼。

　　多關(guān)鍵碼排序按照從最主位關(guān)鍵碼到最次位關(guān)鍵碼或從最次位到最主位關(guān)鍵碼的順序逐次排序，分兩種方法：

　　最高位優(yōu)先(Most Significant Digit first)法，簡(jiǎn)稱MSD法：先按k1排序分組，同一組中記錄，關(guān)鍵碼k1相等，再對(duì)各組按k2排序分成子組，之后，對(duì)后面的關(guān)鍵碼繼續(xù)這樣的排序分組，直到按最次位關(guān)鍵碼kd對(duì)各子組排序后。再將各組連接起來，便得到一個(gè)有序序列。撲克牌按花色、面值排序中介紹的方法一即是MSD法。

　　最低位優(yōu)先(Least Significant Digit first)法，簡(jiǎn)稱LSD法：先從kd開始排序，再對(duì)kd-1進(jìn)行排序，依次重復(fù)，直到對(duì)k1排序后便得到一個(gè)有序序列。撲克牌按花色、面值排序中介紹的方法二即是LSD法。

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