1、第三章查找與排序(下),本節(jié)內(nèi)容,通過本單元的學(xué)習(xí)，了解、掌握有關(guān)排序的： 基本概念： 排序、排序分類、算法穩(wěn)定性 典型的排序算法: 插入排序、選擇排序、交換排序 歸并排序、基數(shù)排序,排序的基本概念,定義：將記錄按關(guān)鍵字遞增(遞減)的次序排列起來，形成新的有序序列，稱為排序。 描述： 設(shè)n個(gè)記錄的序列為R1,R2,Rn,其相應(yīng)關(guān)鍵字序列為K1,K2,Kn,需確定一種排序P1,P2,Pn,使其相應(yīng)的關(guān)鍵字滿足遞增(升序),或遞減(降序)的關(guān)系: Kp1 Kp2 . Kpn 或 Kp1 Kp2 . Kpn,3.3 基本的排序技術(shù),雖然排序算法是一個(gè)簡單的問題，但是從計(jì)算機(jī)科學(xué)發(fā)展以來，已經(jīng)有大量的

2、研究在此問題上。舉例而言，冒泡排序在1956年就已經(jīng)被研究。雖然大部分人認(rèn)為這是一個(gè)已經(jīng)被解決的問題，有用的新算法仍在不斷的被發(fā)明。（例子：圖書館排序在2004年被發(fā)表）,算法穩(wěn)定性,算法穩(wěn)定性,當(dāng)相等的元素是無法分辨的，比如像是整數(shù)，穩(wěn)定性并不是一個(gè)問題。然而，假設(shè)以下的數(shù)對將要以他們的第一個(gè)數(shù)字來排序。 (4, 1) (3, 1) (3, 7) (5, 6) (3, 1) (3, 7) (4, 1) (5, 6) (保持次序) (3, 7) (3, 1) (4, 1) (5, 6) (次序被改變),不穩(wěn)定排序算法可能會(huì)在相等的鍵值中改變紀(jì)錄的相對次序。 不穩(wěn)定排序算法可以被特別地實(shí)現(xiàn)為穩(wěn)定

3、。方法是 人工擴(kuò)充鍵值的比較。然而，要記住這種次序通常牽 涉到額外的空間負(fù)擔(dān)。,簡單起見，這里用順序存儲(chǔ)結(jié)構(gòu)描述待排序的記錄。 順序存儲(chǔ)結(jié)構(gòu)（C語言描述）： #define N n typedef struct record int key ； /* 關(guān)鍵字項(xiàng) */ int otherterm； /* 其它項(xiàng) */ ； typedef struct record RECORD； RECORD fileN+1；/*RECORD型的N+1元數(shù)組*/,排序算法的數(shù)據(jù)結(jié)構(gòu),典型排序算法,冒泡排序 快速排序 簡單插入排序 希爾排序 簡單選擇排序 堆排序 歸并排序 基數(shù)排序 二叉排序樹,一、冒泡排序,1.

4、指導(dǎo)思想： 兩兩比較待排序記錄的關(guān)鍵字，并交換不滿足順序要求的那些偶對元素，直到全部數(shù)列滿足有序?yàn)橹埂?冒泡排序（Bubble sort）是基于交換排序的一種算法。它是依次兩兩比較待排序元素；若為逆序（遞增或遞減）則進(jìn)行交換，將待排序元素從左至右比較一遍稱為一趟“冒泡”。每趟冒泡都將待排序列中的最大關(guān)鍵字交換到最后（或最前）位置。直到全部元素有序?yàn)橹埂?a1 a2 a3 an-1 an,2.冒泡排序算法,step1 從待排序隊(duì)列的前端開始(a1)兩兩比較記錄的關(guān)鍵字值，若aiai+1(i=1,2,n-1)，則交換ai和ai+1的位置，直到隊(duì)列尾部。一趟冒泡處理，將序列中的最大值交換到an的位置

5、。 step2 如法炮制，第k趟冒泡，從待排序隊(duì)列的前端開始(a1)兩兩比較ai和ai+1（i=1 , 2 , n-k)，并進(jìn)行交換處理，選出序列中第k大的關(guān)鍵字值，放在有序隊(duì)列的最前端。(思考：為什么i=1,n-k?) Step3 最多執(zhí)行n-1趟的冒泡處理，序列變?yōu)橛行颉?從小到大排序,冒泡排序算法舉例,設(shè)有數(shù)列 65,97,76,13,27,49,58 比較次數(shù) 第1趟 65，76，13，27，49，58，97 6 第2趟 65，13，27，49，58，76，97 5 第3趟 13，27，49，58，65，76，97 4 第4趟 13，27，49，58，65，76，97 3 第5趟 13

6、，27，49，58，65，76，97 2 第6趟 13，27，49，58，65，76，97 1 總計(jì)： 21 次,3.冒泡排序?qū)崿F(xiàn),bubble(int *item,int count) int a,b，t; for(a=1;aitemb)/*若逆序，則交換*/ t=itemb-1; /* 它們的位置 */ itemb-1=itemb; itemb=t; ,4.改進(jìn)的冒泡排序,從上述舉例中可以看出，從第4趟冒泡起，序列已有序，結(jié)果是空跑了3趟。若兩次冒泡處理過程中，沒有進(jìn)行交換，說明序列已有序，則停止交換。這就是改進(jìn)的冒泡算法的處理思想。 用改進(jìn)的冒泡算法進(jìn)行處理，比較次數(shù)有所減少。 對于數(shù)列

7、 65,97,76,13,27,49,58 比較次數(shù) 第1趟 65，76，13，27，49，58，97 6 第2趟 65，13，27，49，58，76，97 5 第3趟 13，27，49，58，65，76，97 4 第4趟 13，27，49，58，65，76，97 3 總計(jì)： 18 次,bubble_a(int *item,int count) int a,b,t,c; for(a=1;aitemb)/* 若逆序，則 */ t=itemb-1; /* 交換位置 */ itemb-1=itemb; itemb=t; c=0; /* 若有交換，則 */ /* 改變交換標(biāo)志 */ if(c) bre

8、ak; /* 若沒有交換，則 */ /* 退出處理 */ ,5. 算法評價(jià),若待排序列有序(遞增或遞減)，則只需進(jìn)行一趟冒泡處理即可；若反序，則需進(jìn)行n-1趟的冒泡處理。在最壞的情況下，冒泡算法的時(shí)間復(fù)雜度是O( n2 )。 當(dāng)待排序列基本有序時(shí)，采用冒泡排序法效果較好。 冒泡排序算法是穩(wěn)定的。,課堂練習(xí),對下列數(shù)據(jù)進(jìn)行冒泡排序 23 ,34,69,21,5,66,7,8,12,34,二、快速排序,快速排序法是對冒泡排序法的一種改進(jìn)，也是基于交換排序的一種算法。因此，被稱為“分區(qū)交換排序”。 快速排序法是一位計(jì)算機(jī)科學(xué)家C.A.R.Hoare推出并命名的。曾被認(rèn)為是最好的一種排序方法。,1.快

9、速排序基本思想,在待排序序列中按某種方法選取一個(gè)元素K，以它為分界點(diǎn)，用交換的方法將序列分為兩個(gè)部分：比該值小的放在左邊，否則放在右邊。形成 左子序列K右子序列 再分別對左、右兩部分實(shí)施上述分解過程，直到各子序列長度為1，即有序?yàn)橹埂?分界點(diǎn)元素值K的選取方法不同，將構(gòu)成不同的排序法，也將影響排序的效率： 取左邊第1個(gè)元素為分界點(diǎn)； 取中點(diǎn)A（left+right）/2為分界點(diǎn)； 選取最大和最小值的平均值為分界點(diǎn)等。,2. 快速排序算法,Step1 分別從兩端開始，指針i指向第一個(gè)元素Aleft，指針j指向最后一個(gè)元素Aright，分界點(diǎn)取K； Step2 循環(huán)（ij） 從左邊開始進(jìn)行比較：

10、若K Ai，則 i=i+1，再進(jìn)行比較； 若K Ai，則將Ai交換到右邊。 從右邊開始進(jìn)行比較： 若K Aj，則將Aj交換到左邊； 若K Aj ，則 j=j-1，再進(jìn)行比較； 當(dāng)i=j時(shí)，一次分解操作完成。 Step3 在對分解出的左、右兩個(gè)子序列按上述步驟繼續(xù)進(jìn)行分解，直到子序列長度為1（不可再分）為止，也即序列全部有序。,qs(int *item,int left,int right) int i,j,x,y,k; i=left; j=right; x=item(left+right)/2; /* 計(jì)算中點(diǎn)位置 */ do /* ij 的循環(huán)處理 */ while(itemileft) j

11、-; /* 確定j點(diǎn)交換位置 */ if(i=j) /* 如果i、j位置合法，則交換 */ y=itemi; /* Ai和Aj的位置 */ itemi=itemj; itemj=y; i+; j-; while(i=j); if(leftj) qs(item,left,j); /* 對分割出的左部處理*/ if(iright) qs(item,i,right); /*對分割出的右部處理*/ ,快速排序算法舉例,對于數(shù)列49，38，60，90，70，15，30，49， 采用中點(diǎn)分界法： 初始狀態(tài): 49 38 60 90 70 15 30 49 比較次數(shù) 第1趟 49 38 60 90 70 1

12、5 30 49 49 38 60 90 70 15 30 49 5（i4、j1） 49 38 60 49 70 15 30 90 5（i4、j1） 49 38 60 49 70 15 30 90 小計(jì)：10,i,k = 90,j,i,j,j,i,快速排序算法舉例（續(xù)一）,初始狀態(tài): 49 38 60 49 70 15 30 比較次數(shù) 第2趟 49 38 60 49 70 15 30 2（i1、j1） 30 38 60 49 70 15 49 30 38 60 49 70 15 49 30 38 15 49 70 60 49 30 38 15 49 70 60 49 小計(jì)：8,i,j,k = 4

13、9,j,i,i,3（i2、j1）,j,3（i1、j2）,快速排序算法舉例（續(xù)二）,初始狀態(tài): 30 38 15 比較次數(shù) 第3趟 30 38 15 3（i2、j1） 30， 15 38 小計(jì)：3 第4趟 70 60 49 2（i1、j1） 49 60 70 2（i1、j1） 小計(jì)：4,k = 38,i,j,k = 60,j,i,快速排序算法舉例（續(xù)三）,初始狀態(tài): 30 15 比較次數(shù) 第5趟 30 15 2（i1、j1） 15 30 小計(jì)：2 最后狀態(tài)： 15 30 38 49 49 60 70 90 總計(jì)： 27,k = 30,i,j,課堂練習(xí),P233 3.9 數(shù)據(jù)（2）,4. 算法評價(jià)

14、,分界點(diǎn)選取方法不同，排序效果差異很大； 比較次數(shù)為nlogn，即為：O（nlogn）。 快速排序算法是不穩(wěn)定的。,三、簡單插入排序,1.基本思想： 將n個(gè)元素的數(shù)列分為已有序和無序兩個(gè)部分。 a1，a2，a3，a4，,an a1(1)，a2(1)，a3(1)，a4(1) ,an(1) . a1(n-1)，a2(n-1) ，, an(n-1),有序 無序,每次處理：將無序數(shù)列的第一個(gè)元素與有序數(shù)列的元素從后往前逐個(gè)進(jìn)行比較,找出插入位置,將該元素插入到有序數(shù)列的合適位置中。 從前往后，若比ai小，則放在ai前面 從后往前，若比ai大，則放在ai后邊。,2.插入排序算法步驟,Step1 從有序數(shù)

15、列a1和無序數(shù)列a2,a3,an開始進(jìn)行排序; Step2 處理第i個(gè)元素時(shí)(i=2,3,n),數(shù)列 a1,a2,ai-1是已有序的,而數(shù)列ai,ai+1,an是無序的。用ai與ai-1、a i-2,a1進(jìn)行比較,找出合適的位置將ai插入。（從后往前比較） Step3 重復(fù)Step2，共進(jìn)行n-1的插入處理，數(shù)列全部有序。（從小到大排序）,插入排序舉例,設(shè)有數(shù)列 18，12，10，12，30，16 初始狀態(tài)：18，12，10，12，30，16 比較次數(shù) i=1 18，12，10，12，30，16 1 i=2 12，18，10，12，30，16 2 i=3 10，12，18，12，30，16 2

16、 i=4 10，12，12，18，30，16 1 i=5 10，12，12，18，30，16 3 10，12，12，16，18，30 總計(jì)： 9 次,插入排序算法實(shí)現(xiàn),insert_sort(item , n ) int *item ， n ； int i，j，t ； for（i=1；i=0 / 插入該元素 ,4. 算法評價(jià),插入算法比較次數(shù)和交換次數(shù)約為 n2/2，因此，其時(shí)間復(fù)雜度為O（ n2 ）。 該算法是穩(wěn)定的。,四.希爾（Shell）排序,1.思想： 希爾排序是一種快速排序法，出自D.L.Shell, 指導(dǎo)思想： 仍采用插入法，排序過程通過調(diào)換并移動(dòng)數(shù)據(jù)項(xiàng)來實(shí)現(xiàn)。每次比較指定間距的兩

17、個(gè)數(shù)據(jù)項(xiàng)，若右邊的值小于左邊的值，則交換它們的位置。間距d按給定公式減少： di+1 =（di +1）/2 ，直到d等于1為止。d取9，5，3，2，1。,2. 算法步驟,Step1 將n個(gè)元素的數(shù)列分為m個(gè)部分，元素比較間距為d。 Step2 在第i步，兩元素比較的間距取 di+1 =（di +1）/2 9，5，3，2，1 若 ai ai+1 ，則交換它們的位置。 Step3 重復(fù)上述步驟，直到dK = 1。,希爾排序例子,d=5,d=3,插入排序,最后以1步長進(jìn)行排序 （此時(shí)就是簡單的插入排序了）,希爾排序是基于插入排序的以下兩點(diǎn)性質(zhì)而提出改進(jìn)方法的： 1）插入排序在對幾乎已經(jīng)排好序的數(shù)據(jù)操

18、作時(shí)， 效率高， 即可以達(dá)到線性排序的效率； 2）但插入排序一般來說是低效的， 因?yàn)椴迦肱判蛎看沃荒軐?shù)據(jù)移動(dòng)一位。,3. SHELL排序算法(c+語言),template shellsort(T item,int n) int i,j,h; T t; h=n/2 ； while(h0) for(i=h;i=0) itemj+h=itemj; j=j-h; itemj+h=t; h=h/2； ,4. 算法評價(jià),希爾排序算法比較次數(shù)約為n1.5，因此，其時(shí)間復(fù)雜度為O（ n1.5 ）。 該算法是不穩(wěn)定的。,希爾排序課堂練習(xí),23 33 21 1 24 14 2 26 90 43 d=5 3 1,

19、五、簡單選擇排序,1.基本思想：每次從待排序的記錄中選出關(guān)鍵字最?。ɑ蜃畲螅┑挠涗洠樞蚍旁谝延行虻挠涗浶蛄械淖詈螅ɑ蜃钋埃┟?，直到全部數(shù)列有序。 a1，a2，a3，a4，,an a1(1)，a2(1)，a3(1)，a4(1),an(1) . a1(n-1)，a2(n-1) ，, an(n-1),有序 無序,2.選擇排序算法步驟,Step1 從原始數(shù)列a1,a2,a3,an開始進(jìn)行排序，比較n-1次，從中選出最小關(guān)鍵字，放在有序數(shù)列中，形成a1、a2,a3,an有序數(shù)列和無序數(shù)列兩部分，完成第1趟排序。 Step2 處理第i趟排序時(shí)(i=2,3,n)，從剩下的n-i+1個(gè)元素中找出最小關(guān)鍵字，

20、放在有序數(shù)列的后面。 Step3 重復(fù)Step2，共進(jìn)行n-1趟的選擇處理，數(shù)列全部有序。,選擇排序舉例,設(shè)有數(shù)列 18，12，10，12，30，16 初始狀態(tài)：，18，12，10，12，30，16 比較次數(shù) i=1 10，18，12，12，30，16 5 i=2 10，12，18，12，30，16 4 i=3 10，12，12，18，30，16 3 i=4 10，12，12，16，18，30 2 i=5 10，12，12，16，18，30 1 總計(jì)： 15 次,3.選擇排序算法,select_sort(int *item,int count) int i, j, k, t; for(i=0;

21、icount-1;+i) / n-1次循環(huán) k=i; / 無序部分第1個(gè)元素 t=itemi; / 及位置 for(j=i+1;jcount;+j) / 尋找最小值循環(huán) if(itemjt) k=j; t=itemj; / 記錄最小值及位置 itemk=itemi; / 交換最小值與有序 itemi=t; / 部分最后1個(gè)元素位置 ,4. 算法評價(jià),每次選出當(dāng)前最小關(guān)鍵字，但沒有為以后的選擇留下任何信息，比較次數(shù)仍為 O（ n2 ）。 選擇排序算法是不穩(wěn)定的。,六、堆排序,堆排序是一種樹型選擇排序。 在排序過程中，將R0到Rn-1看成是一個(gè)完全二叉樹順序存儲(chǔ)結(jié)構(gòu)，利用完全二叉樹中雙親結(jié)點(diǎn)和孩子

22、結(jié)點(diǎn)之間的內(nèi)在關(guān)系來選擇關(guān)鍵字最小記錄。 堆排序分為兩個(gè)步驟： 1、根據(jù)初始輸入，形成初始堆。 2、通過一系列的對象交換和重新調(diào)整進(jìn)行排序。,1. 堆的定義,n個(gè)關(guān)鍵字序列K1, k2, . ,Kn稱為堆，當(dāng)且僅當(dāng)該序列滿足特性：,從堆的定義可以看出，堆實(shí)質(zhì)上是滿足如下性質(zhì)的二叉樹：樹中任一非葉子結(jié)點(diǎn)的關(guān)鍵字均小于或等于它的孩子結(jié)點(diǎn)的關(guān)鍵字。,10,15,56,25,30,70,10,15,56,25,30,70,小根堆示例,70,56,30,25,15,10,70,56,30,25,15,10,大根堆示例,* 2. 建堆,建堆的方法 次序 思想 舉例 實(shí)現(xiàn)算法,(a)只有一個(gè)結(jié)點(diǎn)的樹是堆 (

23、b)而在完全二叉樹中，所有序號i = low(n/2)的結(jié)點(diǎn)都是葉子，因此以這些結(jié)點(diǎn)為根的子樹都已是堆。,（1） 建堆次序,建大根堆,(c) 只需依次將序號為low(n/2) low(n/2)-1， .，1的結(jié)點(diǎn)作為根的子樹都調(diào)整為堆即可。,23,91,24,16,05,88,42,13,n/2,（1） 建堆次序,(2) 建堆方法-“篩選法”,一: 如果Ri的左右子樹已是堆，這兩棵子樹的根分別是各自子樹中關(guān)鍵字最大的結(jié)點(diǎn)。,23,91,24,16,05,88,42,13,二:若根的關(guān)鍵字已是三者（根、左孩子、右孩子）中的最大者，則無須做任何調(diào)整；否則必須將具有最大關(guān)鍵字的孩子與根交換。,23,

24、91,24,16,05,88,42,13,三: 交換之后有可能導(dǎo)致新子樹不再是堆， 需要將新子樹調(diào)整為堆。如此逐層遞推下去，直到調(diào)整到樹葉為止。,42,88,91,13,24,16,05,23,42,88,91,13,24,16,05,23,17, ,14,思考:如果最后一個(gè)節(jié)點(diǎn)不是14，而是12將如何？,例子：關(guān)鍵字序列為 42，13，91，23， 24， 16，05，88，n=8，故從第四個(gè)結(jié)點(diǎn)開始調(diào)整,42,13,91,23,24,16,05,88,42,13,91,23,24,16,05,88,42,13,91,88,24,16,05,23,42,13,91,88,24,16,05,2

25、3,不調(diào)整,42,13,91,88,24,16,05,23,42,13,91,88,24,16,05,23,42,88,91,23,24,16,05,13,42,88,91,23,24,16,05,13,91,88,42,23,24,16,05,13,91,88,42,23,24,16,05,13,建成的堆,42,13,91,88,24,16,05,23,42,13,91,88,24,16,05,23,m = 2 hm = t = 13 j= 4 hj=88 hj+1 =24,j,m,SIFT(ET h, int n; int m) int j; ET t; t=hm; j=2 * m; wh

26、ile (j = n) /處理到葉子 if (jn) ,SIFT(ET h, int n; int m) int j; ET t; t=hm; j=2 * m; while (j = n) /處理到葉子 if (jn) ,42,91,88,24,16,05,23,42,88,91,88,24,16,05,23,m = 4 t = 13 hm = 13 j= 8 hj=23 hn+1 =0,13,j,m,SIFT(ET h, int n; int m) int j; ET t; t=hm; j=2 * m; while (j=n) /處理到葉子 if (jn) ,42,91,88,24,16,0

27、5,13,42,13,91,88,24,16,05,23,m = 8 t = 13 hm = 23 j= 16,23,j,m,上述算法只是對一個(gè)指定的結(jié)點(diǎn)進(jìn)行調(diào)整。有了這個(gè)算法，將初始的無序區(qū)R1到Rn建成一個(gè)大根堆，如何實(shí)現(xiàn)?,for (i = n/2 1; i=0; i-) SIFT(R, n -1, i),由于建堆的結(jié)果把關(guān)鍵字最大的記錄選到了堆頂?shù)奈恢?，而排序的結(jié)果應(yīng)是升序，如何解決?,3.堆排序算法,應(yīng)該將R0和Rn-1交換，這就得到了第一趟排序的結(jié)果。,第二趟排序的操作首先是將無序區(qū)R0到Rn-2調(diào)整為堆。這時(shí)對于當(dāng)前堆來說，它的左右子樹仍然是堆，所以，可以調(diào)用SIFT函數(shù)將R0到

28、Rn-2調(diào)整為大根堆，選出最大關(guān)鍵字放入堆頂，然后將堆頂與當(dāng)前無序區(qū)的最后一個(gè)記錄Rn-2交換，如此反復(fù)進(jìn)行下去。,91,88,42,23,24,16,05,13,91,88,42,23,24,16,05,13,（a）初始堆R1到R8,舉例：,13,88,42,23,24,16,05,91,13,88,42,23,24,16,05,91,（b）第一趟排序之后,（c）重建的堆R1到R7,88,24,42,23,13,16,05,91,88,24,42,23,13,16,05,91,05,24,42,23,13,16,88,91,05,24,42,23,13,16,88,91,（d）第二趟排序之后

29、,（e）重建的堆R1到R6,42,24,16,23,13,05,88,91,42,24,16,23,13,05,88,91,（f）第三趟排序之后,05,24,16,23,13,42,88,91,05,24,16,23,13,42,88,91,（g）重建的堆R1到R5,24,23,16,05,13,42,88,91,24,23,16,05,13,42,88,91,（h）第四趟排序之后,13,23,16,05,24,42,88,91,13,23,16,05,24,42,88,91,（i）重建的堆R1到R4,23,13,16,05,24,42,88,91,23,13,16,05,24,42,88,9

30、1,（j）第五趟排序之后,05,13,16,23,24,42,88,91,05,13,16,23,24,42,88,91,（k）重建的堆R1到R3,16,13,05,23,24,42,88,91,16,13,05,23,24,42,88,91,（l）第六趟排序之后,05,13,16,23,24,42,88,91,05,13,16,23,24,42,88,91,（m）重建的堆R1到R2,13,05,16,23,24,42,88,91,13,05,16,23,24,42,88,91,（n）第七趟排序之后,05,13,16,23,24,42,88,91,05,13,16,23,24,42,88,91

31、,HEAPSORT(ET p) int i; ET t; for (i=n/2 -1;i=1;i-) sift(p, n-1, i); for (i=n-1;i=1;i-) t=p0; p0=pi; pi=t; sift(p, i-1, 0); ,4.堆排序的時(shí)間復(fù)雜度,堆排序的時(shí)間復(fù)雜性為O(nlog2n) 空間復(fù)雜性為 O(1) 堆排序是不穩(wěn)定的排序方法。,堆排序課堂練習(xí),23 33 21 1 24 14 2 26 90 43 1）先建大根堆（寫出過程） 2）排序！,七、歸并排序,基本原理：通過對兩個(gè)有序結(jié)點(diǎn)序列的合并來實(shí)現(xiàn)排序。 所謂歸并是指將若干個(gè)已排好序的部分合并成一個(gè)有序的部分。

32、若將兩個(gè)有序表合并成一個(gè)有序表，稱為2-路歸并。,1.兩路歸并的基本思想,(1) 設(shè)有兩個(gè)有序表A和B，對象個(gè)數(shù)分別為al和bl，變量i和j分別是兩表的當(dāng)前指針。,(2) 設(shè)表C是歸并后的新有序表，變量k是它的當(dāng)前指針。,(3) i和j對A和B遍歷時(shí)，依次將關(guān)鍵字小的對象放到C中，當(dāng)A或B遍歷結(jié)束時(shí)，將另一個(gè)表的剩余部分照抄到新表中。,兩路歸并的示例,25 57 48 37 12 92 86,25 57 37 48 12 92 86,25 37 48 57 12 86 92,12 25 37 48 57 86 92,歸并排序就是利用上述歸并操作實(shí)現(xiàn)排序的。 (1)將待排序列R1到Rn看成n個(gè)長

33、度為1的有序子序列，把這些子序列兩兩歸并，便得到high(n/2)個(gè)有序的子序列。 (2)然后再把這high(n/2)個(gè)有序的子序列兩兩歸并，如此反復(fù)，直到最后得到一個(gè)長度為n的有序序列。 (3)上述每次歸并操作，都是將兩個(gè)子序列歸并為一個(gè)子序列，這就是“二路歸并”，類似地還可以有“三路歸并”或“多路歸并”。,算法評價(jià),空間復(fù)雜度為O（ n ）， 用輔助空間L1、L2、（Swap） 時(shí)間復(fù)雜度為O（nlogn） 2-路歸并排序算法是穩(wěn)定的。,八、基數(shù)排序,多關(guān)鍵字排序技術(shù)：多關(guān)鍵字（ K1 ,K2, Kt ）; 例如：關(guān)鍵字 K1 小的結(jié)點(diǎn)排在前面。如關(guān)鍵字 K1相同，則比較關(guān)鍵字 K2 ，關(guān)

34、鍵字 K2 小的結(jié)點(diǎn)排在前面，依次類推,1.舉例,假定給定的是 t = 2 位十進(jìn)制數(shù)，存放在數(shù)組 B 之中?，F(xiàn)要求通過基數(shù)排序法將其排序。 設(shè)置十個(gè)口袋，因十進(jìn)制數(shù)分別有數(shù)字：0，1，2，9 ，分別用 B0、B1、B2、B9 進(jìn)行標(biāo)識(shí)。 執(zhí)行 j = 1t (這里t = 2 )次循環(huán)，每次進(jìn)行一次分配動(dòng)作，一次收集動(dòng)作。 將右起第 j 位數(shù)字相同的數(shù)放入同一口袋。比如數(shù)字為 1 者，則放入口袋B1，余類推 收集：按 B0、B1、B2、 B9 的順序進(jìn)行收集。,基數(shù)排序舉例,e.g: B = 5、2、9、7、18、17、52 用基數(shù)排序法進(jìn)行排序。 B = 5、2、9、7、18、17、52,B

35、0 B1 B2 B3 B4 B5 B6 B7 B8 B9,口袋,根據(jù) 所指向的 數(shù)，進(jìn)行分配動(dòng)作， 將其分配到相應(yīng)的口 袋。,基數(shù)排序舉例,e.g: B = 5、2、9、7、18、17、52 用基數(shù)排序法進(jìn)行排序。 B = 5、2、9、7、18、17、52,B0 B1 B2 B3 B4 B5 B6 B7 B8 B9,口袋,根據(jù) 所指向的 數(shù)，進(jìn)行分配動(dòng)作， 將其分配到相應(yīng)的口 袋。,5,基數(shù)排序舉例,e.g: B = 5、2、9、7、18、17、52 用基數(shù)排序法進(jìn)行排序。 B = 5、2、9、7、18、17、52,B0 B1 B2 B3 B4 B5 B6 B7 B8 B9,口袋,根據(jù) 所指向

36、的 數(shù)，進(jìn)行分配動(dòng)作， 將其分配到相應(yīng)的口 袋。,5,基數(shù)排序舉例,e.g: B = 5、2、9、7、18、17、52 用基數(shù)排序法進(jìn)行排序。 B = 5、2、9、7、18、17、52,B0 B1 B2 B3 B4 B5 B6 B7 B8 B9,口袋,根據(jù) 所指向的 數(shù)，進(jìn)行分配動(dòng)作， 將其分配到相應(yīng)的口 袋。,5,2,基數(shù)排序舉例,e.g: B = 5、2、9、7、18、17、52 用基數(shù)排序法進(jìn)行排序。 B = 5、2、9、7、18、17、52,B0 B1 B2 B3 B4 B5 B6 B7 B8 B9,口袋,根據(jù) 所指向的 數(shù)，進(jìn)行分配動(dòng)作， 將其分配到相應(yīng)的口 袋。,5,2,基數(shù)排序舉

37、例,e.g: B = 5、2、9、7、18、17、52 用基數(shù)排序法進(jìn)行排序。 B = 5、2、9、7、18、17、52,B0 B1 B2 B3 B4 B5 B6 B7 B8 B9,口袋,根據(jù) 所指向的 數(shù)，進(jìn)行分配動(dòng)作， 將其分配到相應(yīng)的口 袋。,5,2,9,基數(shù)排序舉例,e.g: B = 5、2、9、7、18、17、52 用基數(shù)排序法進(jìn)行排序。 B = 5、2、9、7、18、17、52,B0 B1 B2 B3 B4 B5 B6 B7 B8 B9,口袋,根據(jù) 所指向的 數(shù)，進(jìn)行分配動(dòng)作， 將其分配到相應(yīng)的口 袋。,5,2,9,基數(shù)排序舉例,e.g: B = 5、2、9、7、18、17、52

38、用基數(shù)排序法進(jìn)行排序。 B = 5、2、9、7、18、17、52,B0 B1 B2 B3 B4 B5 B6 B7 B8 B9,口袋,根據(jù) 所指向的 數(shù)，進(jìn)行分配動(dòng)作， 將其分配到相應(yīng)的口 袋。,5,2,9,7,基數(shù)排序舉例,e.g: B = 5、2、9、7、18、17、52 用基數(shù)排序法進(jìn)行排序。 B = 5、2、9、7、18、17、52,B0 B1 B2 B3 B4 B5 B6 B7 B8 B9,口袋,根據(jù) 所指向的 數(shù)，進(jìn)行分配動(dòng)作， 將其分配到相應(yīng)的口 袋。,5,2,9,7,基數(shù)排序舉例,e.g: B = 5、2、9、7、18、17、52 用基數(shù)排序法進(jìn)行排序。 B = 5、2、9、7、

39、18、17、52,B0 B1 B2 B3 B4 B5 B6 B7 B8 B9,口袋,根據(jù) 所指向的 數(shù)，進(jìn)行分配動(dòng)作， 將其分配到相應(yīng)的口 袋。,5,2,9,7,18,基數(shù)排序舉例,e.g: B = 5、2、9、7、18、17、52 用基數(shù)排序法進(jìn)行排序。 B = 5、2、9、7、18、17、52,B0 B1 B2 B3 B4 B5 B6 B7 B8 B9,口袋,根據(jù) 所指向的 數(shù)，進(jìn)行分配動(dòng)作， 將其分配到相應(yīng)的口 袋。,5,2,9,7,18,基數(shù)排序舉例,e.g: B = 5、2、9、7、18、17、52 用基數(shù)排序法進(jìn)行排序。 B = 5、2、9、7、18、17、52,B0 B1 B2

40、B3 B4 B5 B6 B7 B8 B9,口袋,根據(jù) 所指向的 數(shù)，進(jìn)行分配動(dòng)作， 將其分配到相應(yīng)的口 袋。,5,2,9,7,18,17,基數(shù)排序舉例,e.g: B = 5、2、9、7、18、17、52 用基數(shù)排序法進(jìn)行排序。 B = 5、2、9、7、18、17、52,B0 B1 B2 B3 B4 B5 B6 B7 B8 B9,口袋,根據(jù) 所指向的 數(shù)，進(jìn)行分配動(dòng)作， 將其分配到相應(yīng)的口 袋。,5,2,9,7,18,17,基數(shù)排序舉例,e.g: B = 5、2、9、7、18、17、52 用基數(shù)排序法進(jìn)行排序。 B = 5、2、9、7、18、17、52,B0 B1 B2 B3 B4 B5 B6

41、B7 B8 B9,口袋,根據(jù) 所指向的 數(shù)，進(jìn)行分配動(dòng)作， 將其分配到相應(yīng)的口 袋。,5,2,9,7,18,17,52,基數(shù)排序舉例,e.g: B = 5、2、9、7、18、17、52 用基數(shù)排序法進(jìn)行排序。 B = 5、2、9、7、18、17、52,B0 B1 B2 B3 B4 B5 B6 B7 B8 B9,口袋,分配完畢，按照 箭頭所指的方向進(jìn)行 收集動(dòng)作。注意：收 集后的序列已經(jīng)按照 右起第一位（個(gè)位數(shù) 字）排好序了。,5,2,9,7,18,17,52,收集后的序列：2、52、5、7、17、18、9、,基數(shù)排序舉例,e.g: B = 5、2、9、7、18、17、52 用基數(shù)排序法進(jìn)行排序

42、。 B = 2、52、5、7、17、18、9 （第一次收集的結(jié)果）,B0 B1 B2 B3 B4 B5 B6 B7 B8 B9,口袋,根據(jù) 所指向的 數(shù)，進(jìn)行分配動(dòng)作， 將其分配到相應(yīng)的口 袋。和第一次不同， 這次根據(jù)右起第二位 數(shù)字（十位數(shù)字）進(jìn) 分配。,基數(shù)排序舉例,e.g: B = 5、2、9、7、18、17、52 用基數(shù)排序法進(jìn)行排序。 B = 2、52、5、7、17、18、9 （第一次收集的結(jié)果）,B0 B1 B2 B3 B4 B5 B6 B7 B8 B9,口袋,根據(jù) 所指向的 數(shù)，進(jìn)行分配動(dòng)作， 將其分配到相應(yīng)的口 袋。和第一次不同， 這次根據(jù)右起第二位 數(shù)字（十位數(shù)字）進(jìn) 分配。

43、,2,基數(shù)排序舉例,e.g: B = 5、2、9、7、18、17、52 用基數(shù)排序法進(jìn)行排序。 B = 2、52、5、7、17、18、9 （第一次收集的結(jié)果）,B0 B1 B2 B3 B4 B5 B6 B7 B8 B9,口袋,根據(jù) 所指向的 數(shù)，進(jìn)行分配動(dòng)作， 將其分配到相應(yīng)的口 袋。和第一次不同， 這次根據(jù)右起第二位 數(shù)字（十位數(shù)字）進(jìn) 分配。,2,基數(shù)排序舉例,e.g: B = 5、2、9、7、18、17、52 用基數(shù)排序法進(jìn)行排序。 B = 2、52、5、7、17、18、9 （第一次收集的結(jié)果）,B0 B1 B2 B3 B4 B5 B6 B7 B8 B9,口袋,根據(jù) 所指向的 數(shù)，進(jìn)行分

44、配動(dòng)作， 將其分配到相應(yīng)的口 袋。和第一次不同， 這次根據(jù)右起第二位 數(shù)字（十位數(shù)字）進(jìn) 分配。,2,52,基數(shù)排序舉例,e.g: B = 5、2、9、7、18、17、52 用基數(shù)排序法進(jìn)行排序。 B = 2、52、5、7、17、18、9 （第一次收集的結(jié)果）,B0 B1 B2 B3 B4 B5 B6 B7 B8 B9,口袋,根據(jù) 所指向的 數(shù)，進(jìn)行分配動(dòng)作， 將其分配到相應(yīng)的口 袋。和第一次不同， 這次根據(jù)右起第二位 數(shù)字（十位數(shù)字）進(jìn) 分配。,2,52,基數(shù)排序舉例,e.g: B = 5、2、9、7、18、17、52 用基數(shù)排序法進(jìn)行排序。 B = 2、52、5、7、17、18、9 （第一

45、次收集的結(jié)果）,B0 B1 B2 B3 B4 B5 B6 B7 B8 B9,口袋,根據(jù) 所指向的 數(shù)，進(jìn)行分配動(dòng)作， 將其分配到相應(yīng)的口 袋。和第一次不同， 這次根據(jù)右起第二位 數(shù)字（十位數(shù)字）進(jìn) 分配。,2,52,5,基數(shù)排序舉例,e.g: B = 5、2、9、7、18、17、52 用基數(shù)排序法進(jìn)行排序。 B = 2、52、5、7、17、18、9 （第一次收集的結(jié)果）,B0 B1 B2 B3 B4 B5 B6 B7 B8 B9,口袋,根據(jù) 所指向的 數(shù)，進(jìn)行分配動(dòng)作， 將其分配到相應(yīng)的口 袋。和第一次不同， 這次根據(jù)右起第二位 數(shù)字（十位數(shù)字）進(jìn) 分配。,2,52,5,基數(shù)排序舉例,e.g:

46、 B = 5、2、9、7、18、17、52 用基數(shù)排序法進(jìn)行排序。 B = 2、52、5、7、17、18、9 （第一次收集的結(jié)果）,B0 B1 B2 B3 B4 B5 B6 B7 B8 B9,口袋,根據(jù) 所指向的 數(shù)，進(jìn)行分配動(dòng)作， 將其分配到相應(yīng)的口 袋。和第一次不同， 這次根據(jù)右起第二位 數(shù)字（十位數(shù)字）進(jìn) 分配。,2,52,5,7,基數(shù)排序舉例,e.g: B = 5、2、9、7、18、17、52 用基數(shù)排序法進(jìn)行排序。 B = 2、52、5、7、17、18、9 （第一次收集的結(jié)果）,B0 B1 B2 B3 B4 B5 B6 B7 B8 B9,口袋,根據(jù) 所指向的 數(shù)，進(jìn)行分配動(dòng)作， 將其

47、分配到相應(yīng)的口 袋。和第一次不同， 這次根據(jù)右起第二位 數(shù)字（十位數(shù)字）進(jìn) 分配。,2,52,5,7,基數(shù)排序舉例,e.g: B = 5、2、9、7、18、17、52 用基數(shù)排序法進(jìn)行排序。 B = 2、52、5、7、17、18、9 （第一次收集的結(jié)果）,B0 B1 B2 B3 B4 B5 B6 B7 B8 B9,口袋,根據(jù) 所指向的 數(shù)，進(jìn)行分配動(dòng)作， 將其分配到相應(yīng)的口 袋。和第一次不同， 這次根據(jù)右起第二位 數(shù)字（十位數(shù)字）進(jìn) 分配。,2,52,5,7,17,基數(shù)排序舉例,e.g: B = 5、2、9、7、18、17、52 用基數(shù)排序法進(jìn)行排序。 B = 2、52、5、7、17、18、9

48、 （第一次收集的結(jié)果）,B0 B1 B2 B3 B4 B5 B6 B7 B8 B9,口袋,根據(jù) 所指向的 數(shù)，進(jìn)行分配動(dòng)作， 將其分配到相應(yīng)的口 袋。和第一次不同， 這次根據(jù)右起第二位 數(shù)字（十位數(shù)字）進(jìn) 分配。,2,52,5,7,17,基數(shù)排序舉例,e.g: B = 5、2、9、7、18、17、52 用基數(shù)排序法進(jìn)行排序。 B = 2、52、5、7、17、18、9 （第一次收集的結(jié)果）,B0 B1 B2 B3 B4 B5 B6 B7 B8 B9,口袋,根據(jù) 所指向的 數(shù)，進(jìn)行分配動(dòng)作， 將其分配到相應(yīng)的口 袋。和第一次不同， 這次根據(jù)右起第二位 數(shù)字（十位數(shù)字）進(jìn) 分配。,2,52,5,7,17,18,基數(shù)排序舉例,e.g: B = 5、2、9、7、18、17、52 用基數(shù)排序法進(jìn)行排序。 B = 2、52、5、7、17、18、9 （第一次收集的結(jié)果）,B0 B1 B2 B3 B4 B5 B6 B7 B8 B9,口袋,根據(jù) 所指向的 數(shù)，進(jìn)行分配動(dòng)作， 將其分配到相應(yīng)的口 袋。和第一次不同， 這次根據(jù)右起第二位 數(shù)字（十位數(shù)字）進(jìn) 分配。,2,52,5,7,17,18,基數(shù)排序舉例,e.g: B = 5、2、9、7、18、17、52 用基數(shù)排序法進(jìn)