第十章內(nèi)部排序主講：戚玉濤第十章內(nèi)部排序10.1排序概述10.2插入排序10.3交換排序10.4選擇排序10.5歸并排序10.6基數(shù)排序歸并排序歸并:

是將兩個(gè)或兩個(gè)以上的有序表合并成一個(gè)新的有序表。2-路歸并：假設(shè)初始序列有n個(gè)記錄首先把它看成是n個(gè)長度為1的有序子序列(歸并項(xiàng))先做兩兩歸并，得到n/2個(gè)長度為2的歸并項(xiàng)(如果n為奇數(shù)，則最后一個(gè)有序子序列的長度為1)；再做兩兩歸并，…，如此重復(fù)共進(jìn)行l(wèi)og2n趟這樣的歸并，最后得到一個(gè)長度為n的有序序列。212525*25*936272083716544921254962930872163754212525*490862729316375408082116252125*254925*623772499354163754627293h=1h=2h=4h=8h=16采用2-路歸并排序方法進(jìn)行排序的過程(11個(gè)記錄)。

1趟歸并后2趟歸并后3趟歸并后4趟歸并后

一趟歸并進(jìn)行n/(2*h)

次兩個(gè)有序子表的歸并操作Merge.將有序的SR[i..m]和SR[m+1..n]歸并為有序的TR[i..n].voidMerge(RcdTypeSR[],RcdType&TR[],inti,intm,intn){for(j=m+1,k=i;i<=m&&j<=n;++k){

if(SR[i].key<=SR[j].key)TR[k]=SR[i++];

elseTR[k]=SR[j++];}if(i<=m)TR[k..n]=SR[i..m];if(j<=n)TR[k..n]=SR[j..n];}有序子表長度分別為：n,m.則Merge的時(shí)間復(fù)雜度為：O(n+m).voidMergePass(RcdTypeSR[],RcdType&TR[],inth,intn){for(i=1;i+2*h-1<=n;i=i+2*h)//歸并h長的兩相鄰子表

Merge(SR,TR,i,i+h-1,i+2*h-1);if(i+h-1<=n)//余下部分

Merge(SR,TR,i,i+h-1,n);}迭代的歸并排序算法（一趟歸并排序的情形）voidMergeSort(SqList&L)//自底向上的二路歸并算法 {RcdTypeTR[];for(h=1;h<L.length;h=2*h) {MergePass(L.r,TR,h,L.length); L.r[1..L.length]=TR[1..L.length]; }}Merge調(diào)用n/(2*h)次MergePass調(diào)用log2n

次算法總的時(shí)間復(fù)雜度:O(nlog2n)歸并排序歸并排序的時(shí)間復(fù)雜度為O(nlog2n)歸并排序是一個(gè)穩(wěn)定的排序方法。第十章內(nèi)部排序10.1排序概述10.2插入排序10.3交換排序10.4選擇排序10.5歸并排序10.6基數(shù)排序基數(shù)排序基數(shù)排序：是通過“分配”和“收集”過程來實(shí)現(xiàn)排序，是一種借助于多關(guān)鍵字排序的思想對(duì)單關(guān)鍵字排序的方法。實(shí)現(xiàn)多關(guān)鍵字排序有兩種常用的方法最高位優(yōu)先法MSD(MostSignificantDigitfirst)最低位優(yōu)先法LSD(LeastSignificantDigitfirst)多關(guān)鍵字排序最高位優(yōu)先法MSD先根據(jù)最高位關(guān)鍵字K1排序,得到若干組，每組中每個(gè)記錄都有相同關(guān)鍵字K1。再分別對(duì)每組中記錄根據(jù)關(guān)鍵字K2進(jìn)行排序，按K2值的不同，再分成若干個(gè)更小的子組，每個(gè)子組中的記錄具有相同的K1和K2值。依此重復(fù)，直到對(duì)關(guān)鍵字Kd完成排序?yàn)橹埂Ｗ詈?，把所有子組中的記錄依次連接起來，就得到一個(gè)有序的序列。撲克牌排序方法二：先排花色，再排數(shù)字－－最高位優(yōu)先???1?2?1?5?4?2?5?3?3?2?5?2?1?1?4?3?5?3?4?4??4?4?4?4?2?3?3?3?3?2?2?2?1?1?1?1?5?5?5?5?3?2????1?2?1?5?4?2?5?3?5?2?1?1?4?3?5?3?4?4?????5?5?5?4?5?4?4?4?3?2?3?3?3?2?1?2?1?2?1?1??多關(guān)鍵字排序最低位優(yōu)先法LSD首先依據(jù)最低位關(guān)鍵字Kd對(duì)所有記錄進(jìn)行一趟排序；再依據(jù)次低位關(guān)鍵字Kd-1對(duì)上一趟排序的結(jié)果再排序；依次重復(fù)，直到依據(jù)關(guān)鍵字K1最后一趟排序完成，就可以得到一個(gè)有序的序列。舉例：撲克牌排序方法一：先排數(shù)字，再排花色－－最低位優(yōu)先324151?1?1?1?2?2?2?2?3?3?3?3?4?4?4?5?5?5?5?4?4?4?4?2?3?3?3?3?2?2?2?1?1?1?1?5?5?5?5?4?132451?1?1?1?2?2?2?2?3?3?3?3?4?4?4?5?5?5?5?4?1?1?5?2?1?2?4?3?2?3?3?5?4?5?2?4?4?3?1?5????5?5?5?4?5?4?4?4?3?2?3?3?3?2?1?2?1?2?1?1?????5?5?5?4?5?4?4?4?3?2?3?3?3?2?1?2?1?2?1?1??鏈?zhǔn)交鶖?shù)排序如果關(guān)鍵字是多位十進(jìn)制數(shù)，我們可以將每位數(shù)看成為一個(gè)關(guān)鍵字：比如：關(guān)鍵字Key是0～999的三位數(shù)，可認(rèn)為Key由三個(gè)關(guān)鍵字(K0,K1,K2)組成，每個(gè)Ki的基數(shù)是10（可取0～9中的任一個(gè)值）如果關(guān)鍵字是由若干個(gè)字母組成的單詞，我們可以將每位字母看成是一個(gè)關(guān)鍵字：比如：關(guān)鍵字Key是由3個(gè)小寫字母組成的單詞，則Key由5個(gè)關(guān)鍵字(K0,K1,K2)組成，每個(gè)Ki的基數(shù)是26（可取‘a(chǎn)’～‘z’中的任一個(gè)字符）鏈?zhǔn)交鶖?shù)排序基數(shù)排序是典型的最低位優(yōu)先法排序方法，利用“分配”和“收集”兩種運(yùn)算對(duì)單關(guān)鍵字進(jìn)行排序。在這種方法中，把單關(guān)鍵字Ki看成是一個(gè)d元組：分量有radix種取值，則稱radix為基數(shù)，即分量的取值范圍。記錄的關(guān)鍵字K0,K1,…,Kd-1，依次對(duì)各位的分量，分別用“分配”、“收集”的運(yùn)算逐趟進(jìn)行排序。鏈?zhǔn)交鶖?shù)排序各隊(duì)列采用鏈?zhǔn)疥?duì)列結(jié)構(gòu)，分配到同一隊(duì)列的關(guān)鍵字用指針鏈接起來。每一隊(duì)列設(shè)置兩個(gè)指針:front[radix]指示隊(duì)頭，rear[radix]指向隊(duì)尾。以靜態(tài)鏈表作為n個(gè)記錄的存儲(chǔ)結(jié)構(gòu)。在記錄重排時(shí)不必移動(dòng)記錄，只需修改各記錄的鏈接指針即可。例，序列：

278109063930589184505269008083第一趟分配0123456789278109063930589184505269008083第一趟收集930063083184505278008109589269第二趟分配0123456789930063083184505278008109589269第二趟收集505008109930063269278083184589第二趟收集505008109930063269278083

184589第三趟分配0123456789505008109930063269278083184589第三趟收集008063083109184269278505589930基數(shù)排序若每個(gè)關(guān)鍵字有d位，需要重復(fù)執(zhí)行d趟“分配”與“收集”。每趟對(duì)n個(gè)記錄進(jìn)行“分配”，對(duì)radix個(gè)隊(duì)列進(jìn)行“收集”。總時(shí)間復(fù)雜度為

O(d(n+radix))?；鶖?shù)排序是穩(wěn)定的排序方法。各種內(nèi)部排序方法的比較關(guān)于排序算法的結(jié)論若n較小，可采用直接插入排序或簡單選擇排序若序列的初始狀態(tài)已按關(guān)鍵字基本有序，則選用直接插入或起泡排序?yàn)橐耍蝗鬾較大，采用O(nlog2n)的排序方法；若n很大，記錄的關(guān)鍵字位數(shù)較少且可以分解時(shí)，采用基數(shù)排序較好；避免移動(dòng)記錄，用