歸并排序-課件

10.5歸并排序基本思想將兩個(gè)或兩個(gè)以上的有序子序列“歸并”為一個(gè)有序序列。在內(nèi)部排序中，通常采用的是2-路歸并排序。即：將兩個(gè)位置相鄰的有序子序列歸并為一個(gè)有序序列。r[i]r[m]r[m+1]r[n]有序有序有序r[i]r[n]10.5歸并排序基本思想r[i]r[110.5歸并排序如何進(jìn)行兩路歸并？將兩個(gè)有序表的元素進(jìn)行比較，小者復(fù)制到目標(biāo)表中。（5，24，35，74，222）（19，23，30）()10.5歸并排序如何進(jìn)行兩路歸并？（5，24，35，7425243574222()192330()ij()k5192324303574222兩路歸并動(dòng)畫(huà)演示ikjkjkikjk[s][m][t][m+1]5243574222()192330()ij()k51923310.5歸并排序voidMerge(intr[],intr1[],ints,intm,intt){/***將有序列r[s..m]和r[m+1..t]兩路歸并為r1[]***/i=s;j=m+1;k=s;while(i<=m&&j<=t){//兩表中元素比較if(r[i]<=r[j])r1[k++]=r[i++];elser1[k++]=r[j++];}while(i<=m)r1[k++]=r[i++];//前一個(gè)子序列剩下的while(j<=t)r1[k++]=r[j++];//后一個(gè)子序列剩下的}10.5歸并排序voidMerge(intr[]410.5歸并排序原理假設(shè)初始序列含有n個(gè)記錄，則可看成n個(gè)有序的子序列，每個(gè)子序列長(zhǎng)度為1。然后兩兩歸并，得到n/2個(gè)長(zhǎng)度為2或1的有序子序列；再兩兩歸并，……如此重復(fù)，直至得到一個(gè)長(zhǎng)度為n的有序序列為止。初始時(shí)：[49][38][65][97][76][13][27]10.5歸并排序原理初始時(shí)：[49][385初始關(guān)鍵字：[49][38][65][97][76][13][27]一趟歸并后：[3849][6597][1376][27]二趟歸并后：[38496597][132776]三趟歸并后：[13273849657697]初始關(guān)鍵字：[49][38][65]6voidMsort(ElemSR[],ElemTR1[],ints,intt){

/****將SR[s..t]進(jìn)行歸并排序?yàn)門(mén)R1[s..t]****/

if(s==t)TR1[s]=SR[s];

else{m=(s+t)/2;//將SR[s..t]分割Msort(SR,TR1,s,m);//遞歸地排序子序列SR[s..m]Msort(SR,TR2,m+1,t);//遞歸地排序子序列SR[m+1..t]Merge(TR2,TR1,s,m,t);//歸并

}}

10.5歸并排序voidMsort(ElemSR[],ElemT710.5歸并排序性能分析一趟歸并操作是將r[1]~r[n]中相鄰的長(zhǎng)度為h的有序序列進(jìn)行兩兩歸并，這需要O(n)時(shí)間。整個(gè)歸并排序需要進(jìn)行l(wèi)og2n趟，因此，總的時(shí)間代價(jià)是O(nlog2n)。10.5歸并排序性能分析810.5歸并排序性能分析算法在執(zhí)行時(shí)，需要占用與原始記錄序列同樣數(shù)量的存儲(chǔ)空間，因此空間復(fù)雜度為O(n)。10.5歸并排序性能分析910.5歸并排序總結(jié)最好、最壞、平均時(shí)間復(fù)雜度均為O(nlogn);空間復(fù)雜度高，為O(n);是高效算法中唯一“穩(wěn)定”的排序方法；較少用于內(nèi)部排序，多用于外部排序。10.5歸并排序總結(jié)1010.6基數(shù)排序基本思想基數(shù)排序是采用“分配”與“收集”的辦法，用對(duì)多關(guān)鍵碼進(jìn)行排序的思想實(shí)現(xiàn)對(duì)單關(guān)鍵碼進(jìn)行排序的方法。10.6基數(shù)排序基本思想基數(shù)排序1110.6基數(shù)排序多關(guān)鍵碼排序問(wèn)題以撲克牌排序?yàn)槔?。每張撲克牌有兩個(gè)“關(guān)鍵碼”：花色和面值。其有序關(guān)系為：花色：

面值：2<3<4<5<6<7<8<9<10<J<Q<K<A10.6基數(shù)排序多關(guān)鍵碼排序問(wèn)題以撲克牌排1210.6基數(shù)排序“花色”優(yōu)先先分成4堆；然后，每堆再按“面值”排；最后，收成一堆。撲克牌“排序”為例10.6基數(shù)排序“花色”優(yōu)先撲克牌“排序”為例1310.6基數(shù)排序“面值”優(yōu)先先分成13堆；每堆再按“花色”排；

撲克牌“排序”為例10.6基數(shù)排序“面值”優(yōu)先撲克牌“排序”為例1410.6基數(shù)排序多關(guān)鍵碼排序假設(shè)有n個(gè)記錄……的序列

{R1,R2,…，Rn}每個(gè)記錄Ri中含有d個(gè)關(guān)鍵字(Ki0,Ki1,…,Kid-1)。則有序是指：對(duì)于序列中任意兩個(gè)記錄Ri和Rj(1≤i<j≤n)都滿(mǎn)足下列(詞典)有序關(guān)系：(Ki0,Ki1,…,Kid-1)<(Kj0,Kj1,…,Kjd-1)其中K0被稱(chēng)為“最高”位關(guān)鍵字，Kd-1被稱(chēng)為“最低”位關(guān)鍵字。10.6基數(shù)排序多關(guān)鍵碼排序假設(shè)有n個(gè)記錄……的1510.6基數(shù)排序多關(guān)鍵碼排序?qū)崿F(xiàn)多關(guān)鍵碼排序通常有兩種方法：低位碼優(yōu)先LSD高位碼優(yōu)先MSD(3J899

317)先按花色：

8137

J

9

3

9再按面值：

1

837

9

J

3

910.6基數(shù)排序多關(guān)鍵碼排序(3J1610.6.2鏈?zhǔn)交鶖?shù)排序?qū)τ趩侮P(guān)鍵字，可以看成是由多個(gè)數(shù)位構(gòu)成的多關(guān)鍵字；

基數(shù)排序是典型的LSD排序方法，利用“分配”和“收集”兩種運(yùn)算對(duì)單關(guān)鍵碼進(jìn)行排序。例如：對(duì)下列這組關(guān)鍵字（每個(gè)關(guān)鍵字有3位）{209,386,768,185,247,606,230,834,539}10.6.2鏈?zhǔn)交鶖?shù)排序?qū)τ趩侮P(guān)鍵字，可以看成是由多個(gè)1710.6.2鏈?zhǔn)交鶖?shù)排序基本思想從關(guān)鍵字的最“低位”開(kāi)始，將關(guān)鍵字分配到r(基數(shù)）個(gè)堆（桶）中；按桶的編號(hào)將關(guān)鍵字收集起來(lái)；然后，以“次低位”將關(guān)鍵字又分配到r個(gè)桶中；再收集，……，重復(fù)直到“最高位”為止，這時(shí)，以按關(guān)鍵字有序。10.6.2鏈?zhǔn)交鶖?shù)排序基本思想18例如：對(duì)下列這組關(guān)鍵字進(jìn)行基數(shù)排序{209,386,768,185,247,606,230,834,539}基數(shù)為10分別按“個(gè)位”、“十位”、“百位”進(jìn)行3趟分配與收集0123456789例如：對(duì)下列這組關(guān)鍵字進(jìn)行基數(shù)排序基數(shù)為10分別按“個(gè)位”、1910.6.2鏈?zhǔn)交鶖?shù)排序?qū)崿F(xiàn)思想為了便于分配與收集，采用鏈表為存儲(chǔ)結(jié)構(gòu)r個(gè)桶用r個(gè)鏈?zhǔn)疥?duì)列表示；收集的時(shí)候直接將隊(duì)列的頭尾指針連接實(shí)現(xiàn)；10.6.2鏈?zhǔn)交鶖?shù)排序?qū)崿F(xiàn)思想20例初始狀態(tài)：278109063930589184505269008083109589269278063930083184505008r[0]r[1]r[2]r[3]r[4]r[5]r[6]r[7]r[8]r[9]f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]一趟分配930063083184505278008109589269一趟收集：例初始狀態(tài)：27810906393058918450526921505008109930063269278083184589第二趟收集：083184589063505269930r[0]r[1]r[2]r[3]r[4]r[5]r[6]r[7]r[8]r[9]f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]二趟分配008109278930063083184505278008109589269第一趟收集：例50500810993006326927808318458922008063083109184269278505589930第三趟收集：109008184930e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]三趟分配063083269278505589505008109930063269278083184589第二趟收集：例有序0080630831091842692785055899302310.6.2鏈?zhǔn)交鶖?shù)排序//分配//收集基數(shù)排序算法10.6.2鏈?zhǔn)交鶖?shù)排序//分配//收集基數(shù)排序算法2410.6.2鏈?zhǔn)交鶖?shù)排序分配算法10.6.2鏈?zhǔn)交鶖?shù)排序分配算法2510.6.2鏈?zhǔn)交鶖?shù)排序收集算法10.6.2鏈?zhǔn)交鶖?shù)排序收集算法2610.6.2鏈?zhǔn)交鶖?shù)排序性能分析若每個(gè)關(guān)鍵碼有d位，需要重復(fù)執(zhí)行d趟“分配”與“收集”。而每趟對(duì)n個(gè)對(duì)象進(jìn)行“分配”，對(duì)r個(gè)隊(duì)列進(jìn)行“收集”。總時(shí)間復(fù)雜度為O(d(n+r))。若基數(shù)r相同，對(duì)于數(shù)據(jù)個(gè)數(shù)較多而關(guān)鍵碼位數(shù)較少的情況，使用鏈?zhǔn)交鶖?shù)排序較好。需要增加n+2r個(gè)附加鏈接指針。穩(wěn)定的排序方法10.6.2鏈?zhǔn)交鶖?shù)排序性能分析2710.6內(nèi)部排序方法的比較討論對(duì)排序算法應(yīng)該從以下幾個(gè)方面綜合考慮：⑴時(shí)間復(fù)雜性；⑵空間復(fù)雜性；⑶穩(wěn)定性；⑷算法簡(jiǎn)單性；⑸待排序記錄個(gè)數(shù)n的大小；⑹記錄本身信息量的大??；⑺關(guān)鍵碼的分布情況10.6內(nèi)部排序方法的比較討論對(duì)排序算法應(yīng)該從以下幾個(gè)方28排序方法平均情況最好情況最壞情況直接插入排序O(n2)O(n)O(n2)希爾排序O(nlog2n)O(n1.3)O(n2)冒泡排序O(n2)O(n)O(n2)快速排序O(nlog2n)O(nlog2n)O(n2)簡(jiǎn)單選擇排序O(n2)O(n2)O(n2)堆排序O(nlog2n)O(nlog2n)O(nlog2n)歸并排序O(nlog2n)O(nlog2n)O(nlog2n)時(shí)間復(fù)雜度排序方法平均情況最好情況最壞情況直接插入排序O(n2)O(n29排序方法輔助空間直接插入排序O(1)希爾排序O(1)冒泡排序O(1)快速排序O(log2n)~O(n)簡(jiǎn)單選擇排序O(1)堆排序O(1)歸并排序O(n)空間復(fù)雜度排序方法輔助空間直接插入排序O(1)希爾排序O(1)冒泡排序30排序方法輔助空間直接插入排序穩(wěn)定希爾排序不穩(wěn)定冒泡排序穩(wěn)定快速排序不穩(wěn)定簡(jiǎn)單選擇排序穩(wěn)定堆排序不穩(wěn)定歸并排序穩(wěn)定算法穩(wěn)定性排序方法輔助空間直接插入排序穩(wěn)定希爾排序不穩(wěn)定冒泡排序穩(wěn)定快31簡(jiǎn)單性

一類(lèi)是簡(jiǎn)單算