1、第三章查找與排序(下)本節(jié)內(nèi)容通過本單元的學(xué)習(xí)，理解、掌握有關(guān)排序的：基本概念：排序、排序分類、算法穩(wěn)定性典型的排序算法:插入排序、選擇排序、交換排序歸并排序、基數(shù)排序排序的基本概念n定義：將記錄按關(guān)鍵字遞增定義：將記錄按關(guān)鍵字遞增(遞減遞減)的次序排列起來，的次序排列起來，形成新的有序序列，稱為排序。形成新的有序序列，稱為排序。n描繪：描繪：n 設(shè)設(shè)n個(gè)記錄的序列為個(gè)記錄的序列為R1,R2,Rn,其相應(yīng)關(guān)鍵字其相應(yīng)關(guān)鍵字序列為序列為K1,K2,Kn,需確定一種排序需確定一種排序P1,P2,Pn,使其相應(yīng)的關(guān)鍵字滿足遞增使其相應(yīng)的關(guān)鍵字滿足遞增(升序升序),或遞減或遞減(降序降序)的的關(guān)系關(guān)系

2、:n Kp1 Kp2 . Kpn n 或或n Kp1 Kp2 . Kpn3.3 基本的排序技術(shù)n雖然排序算法是一個(gè)簡單的問題，但是雖然排序算法是一個(gè)簡單的問題，但是從計(jì)算機(jī)科學(xué)發(fā)展以來，已經(jīng)有大量的從計(jì)算機(jī)科學(xué)發(fā)展以來，已經(jīng)有大量的研究在此問題上。舉例而言，冒泡排序研究在此問題上。舉例而言，冒泡排序在在1956年就已經(jīng)被研究。雖然大部分人年就已經(jīng)被研究。雖然大部分人認(rèn)為這是一個(gè)已經(jīng)被解決的問題，有用認(rèn)為這是一個(gè)已經(jīng)被解決的問題，有用的新算法仍在不斷的被發(fā)明。（例子：的新算法仍在不斷的被發(fā)明。（例子：圖書館排序在圖書館排序在2019年被發(fā)表）年被發(fā)表）算法穩(wěn)定性0 1 2 3 4 5算法穩(wěn)定性算

3、法穩(wěn)定性n當(dāng)相等的元素是無法分辨的，比如像是整數(shù)，當(dāng)相等的元素是無法分辨的，比如像是整數(shù)，穩(wěn)定性并不是一個(gè)問題。然而，假設(shè)以下的數(shù)穩(wěn)定性并不是一個(gè)問題。然而，假設(shè)以下的數(shù)對將要以他們的第一個(gè)數(shù)字來排序。對將要以他們的第一個(gè)數(shù)字來排序。n(4, 1) (3, 1) (3, 7) (5, 6)n(3, 1) (3, 7) (4, 1) (5, 6) (保持次序保持次序) n(3, 7) (3, 1) (4, 1) (5, 6) (次序被改變次序被改變)n不穩(wěn)定排序算法可能會在相等的鍵值中改變紀(jì)不穩(wěn)定排序算法可能會在相等的鍵值中改變紀(jì)錄的相對次序。錄的相對次序。n不穩(wěn)定排序算法可以被特別地實(shí)現(xiàn)為穩(wěn)定

4、。方不穩(wěn)定排序算法可以被特別地實(shí)現(xiàn)為穩(wěn)定。方法是法是 人工擴(kuò)充鍵值的比較。然而，要記住這人工擴(kuò)充鍵值的比較。然而，要記住這種次序通常牽種次序通常牽 涉到額外的空間負(fù)擔(dān)。涉到額外的空間負(fù)擔(dān)。n簡單起見，這里用順序存儲結(jié)構(gòu)描述待排簡單起見，這里用順序存儲結(jié)構(gòu)描述待排序的記錄。序的記錄。n順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)C語言描述）：語言描述）：n #define N nn typedef struct record n int key ； /* 關(guān)鍵字項(xiàng)關(guān)鍵字項(xiàng) */n int otherterm； /* 其它項(xiàng)其它項(xiàng) */n ；n typedef struct record RECORD；n RECOR

5、D fileN+1；/*RECORD型的型的N+1元數(shù)組元數(shù)組*/排序算法的數(shù)據(jù)結(jié)構(gòu)典型排序算法n冒泡排序冒泡排序n快速排序快速排序n簡單插入排序簡單插入排序n希爾排序希爾排序n簡單選擇排序簡單選擇排序n堆排序堆排序n歸并排序歸并排序n基數(shù)排序基數(shù)排序n二叉排序樹二叉排序樹一、冒泡排序n1.指導(dǎo)思想：指導(dǎo)思想： n 兩兩比較待排序記錄的關(guān)鍵字，并交換不滿足順序要求的兩兩比較待排序記錄的關(guān)鍵字，并交換不滿足順序要求的那些偶對元素，直到全部數(shù)列滿足有序?yàn)橹埂Ｄ切┡紝υ兀钡饺繑?shù)列滿足有序?yàn)橹埂冒泡排序冒泡排序Bubble sort是基于交換排序的一種算法。它是是基于交換排序的一種算法。它是依

6、次兩兩比較待排序元素；若為逆序遞增或遞減則進(jìn)行依次兩兩比較待排序元素；若為逆序遞增或遞減則進(jìn)行交換，將待排序元素從左至右比較一遍稱為一趟交換，將待排序元素從左至右比較一遍稱為一趟“冒泡冒泡”。每。每趟冒泡都將待排序列中的最大關(guān)鍵字交換到最后或最前趟冒泡都將待排序列中的最大關(guān)鍵字交換到最后或最前位置。直到全部元素有序?yàn)橹埂Ｎ恢谩Ｖ钡饺吭赜行驗(yàn)橹埂 n a1 a2 a3 an-1 an 最大值最大值2.冒泡排序算法nstep1 從待排序隊(duì)列的前端開始從待排序隊(duì)列的前端開始(a1)兩兩比較記錄兩兩比較記錄的關(guān)鍵字值，若的關(guān)鍵字值，若aiai+1(i=1,2,n-1)，則交換，則交換ai和和ai

7、+1的位置，直到隊(duì)列尾部。一趟冒泡處理，將的位置，直到隊(duì)列尾部。一趟冒泡處理，將序列中的最大值交換到序列中的最大值交換到an的位置。的位置。nstep2 如法炮制，第如法炮制，第k趟冒泡，從待排序隊(duì)列的前趟冒泡，從待排序隊(duì)列的前端開始端開始(a1)兩兩比較兩兩比較ai和和ai+1i=1 , 2 , n-k)，并，并進(jìn)行交換處理，選出序列中第進(jìn)行交換處理，選出序列中第k大的關(guān)鍵字值，放大的關(guān)鍵字值，放在有序隊(duì)列的最前端。在有序隊(duì)列的最前端。(考慮：為什么考慮：為什么i=1,n-k?)nStep3 最多執(zhí)行最多執(zhí)行n-1趟的冒泡處理，序列變?yōu)橛行颉Ｌ说拿芭萏幚恚蛄凶優(yōu)橛行颉從小到大排序從小到大

8、排序冒泡排序算法舉例設(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，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;acount; a+) /*n-1趟冒泡處理*/ for(b=1

9、;bitemb)/*若逆序，則交換*/ t=itemb-1; /* 它們的位置 */ itemb-1=itemb; itemb=t; 4.改進(jìn)的冒泡排序n從上述舉例中可以看出，從第從上述舉例中可以看出，從第4趟冒泡起，序列已有序，趟冒泡起，序列已有序，結(jié)果是空跑了結(jié)果是空跑了3趟。若兩次冒泡處理過程中，沒有進(jìn)行交趟。若兩次冒泡處理過程中，沒有進(jìn)行交換，說明序列已有序，則停止交換。這就是改進(jìn)的冒泡算換，說明序列已有序，則停止交換。這就是改進(jìn)的冒泡算法的處理思想。法的處理思想。n用改進(jìn)的冒泡算法進(jìn)行處理，比較次數(shù)有所減少。用改進(jìn)的冒泡算法進(jìn)行處理，比較次數(shù)有所減少。n 對于數(shù)列對于數(shù)列 65,97

10、,76,13,27,49,58 比較次數(shù)比較次數(shù)n 第第1趟趟 65，76，13，27，49，58，97 6n n 第第2趟趟 65，13，27，49，58，76，97 5n n 第第3趟趟 13，27，49，58，65，76，97 4n 第第4趟趟 13，27，49，58，65，76，97 3n 總計(jì)：總計(jì)： 18 次次bubble_a(int *item,int count) int a,b,t,c; for(a=1;acount;+a) /* n-1趟的循環(huán) */ c=1; /* 設(shè)置交換標(biāo)志 */ for(b=1;bitemb)/* 若逆序，那么 */ t=itemb-1; /* 交換

11、位置 */ itemb-1=itemb; itemb=t; c=0; /* 若有交換，那么 */ /* 改變交換標(biāo)志 */ if(c) break; /* 若沒有交換，那么 */ /* 退出處理 */ 5. 算法評價(jià)v若待排序列有序若待排序列有序(遞增或遞減遞增或遞減)，則只需進(jìn)，則只需進(jìn)行一趟冒泡處理即可；若反序，則需進(jìn)行行一趟冒泡處理即可；若反序，則需進(jìn)行n-1趟的冒泡處理。在最壞的情況下，冒趟的冒泡處理。在最壞的情況下，冒泡算法的時(shí)間復(fù)雜度是泡算法的時(shí)間復(fù)雜度是O( n2 )。v當(dāng)待排序列基本有序時(shí)，采用冒泡排序法當(dāng)待排序列基本有序時(shí)，采用冒泡排序法效果較好。效果較好。v冒泡排序算法是穩(wěn)

12、定的。冒泡排序算法是穩(wěn)定的。 課堂練習(xí)n對下列數(shù)據(jù)進(jìn)行冒泡排序?qū)ο铝袛?shù)據(jù)進(jìn)行冒泡排序n23 ,34,69,21,5,66,7,8,12,34二、快速排序n快速排序法是對冒泡排序法的一種改進(jìn)，快速排序法是對冒泡排序法的一種改進(jìn)，也是基于交換排序的一種算法。因而，也是基于交換排序的一種算法。因而，被稱為被稱為“分區(qū)交換排序分區(qū)交換排序”。n快 速 排 序 法 是 一 位 計(jì) 算 機(jī) 科 學(xué) 家快 速 排 序 法 是 一 位 計(jì) 算 機(jī) 科 學(xué) 家C.A.R.Hoare推出并命名的。曾被認(rèn)為推出并命名的。曾被認(rèn)為是最好的一種排序方法。是最好的一種排序方法。1.快速排序基本思想n在待排序序列中按某種方

13、法選取一個(gè)元素在待排序序列中按某種方法選取一個(gè)元素K，以它為分界點(diǎn)，以它為分界點(diǎn)，用交換的方法將序列分為兩個(gè)部分：比該值小的放在左邊，用交換的方法將序列分為兩個(gè)部分：比該值小的放在左邊，否則放在右邊。形成否則放在右邊。形成n 左子序列左子序列K右子序列右子序列n 再分別對左、右兩部分實(shí)施上述分解過程，直到各子序列再分別對左、右兩部分實(shí)施上述分解過程，直到各子序列長度為長度為1，即有序?yàn)橹埂＃从行驗(yàn)橹埂分界點(diǎn)元素值分界點(diǎn)元素值K的選取方法不同，將構(gòu)成不同的排序法，也的選取方法不同，將構(gòu)成不同的排序法，也將影響排序的效率：將影響排序的效率：n取左邊第取左邊第1個(gè)元素為分界點(diǎn)；個(gè)元素為分界點(diǎn)；n

14、取中點(diǎn)取中點(diǎn)A（left+right）/2為分界點(diǎn)；為分界點(diǎn)；n選取最大和最小值的平均值為分界點(diǎn)等。選取最大和最小值的平均值為分界點(diǎn)等。2. 快速排序算法nStep1 分別從兩端開始，指針i指向第一個(gè)元素Aleft，指針j指向最后一個(gè)元素Aright，分界點(diǎn)取K；nStep2 循環(huán)ij）n從左邊開始進(jìn)行比較：n 若K Ai，那么 i=i+1，再進(jìn)行比較；n 若K Ai，則將Ai交換到右邊。n從右邊開始進(jìn)行比較：n 若K Aj，則將Aj交換到左邊；n 若K Aj ，那么 j=j-1，再進(jìn)行比較；n當(dāng)i=j時(shí)，一次分解操作完成。nStep3 在對分解出的左、右兩個(gè)子序列按上述步驟繼續(xù)進(jìn)行分解，直到

15、子序列長度為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(itemix & iright ) i+ ； /* 確定i點(diǎn)交換位置 */ while(xleft) j-; /* 確定j點(diǎn)交換位置 */ if(i=j) /* 如果i、j位置合法，則交換 */ y=itemi; /* Ai和Aj的位置 */ itemi=itemj; itemj=y; i+; j

16、-; 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 15 30 49 49 38 60 90 70 15 30 49 5i4、j1） 49 38 60 49 70 15 30 90 5i4、j1） 49 38 60 49 70 15 30

17、90 小計(jì)：10 ik = 90jij ji快速排序算法舉例續(xù)一） 初始狀態(tài): 49 38 60 49 70 15 30 比較次數(shù) 第2趟 49 38 60 49 70 15 30 2i1、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ì)：8ijk = 49jii3 3i2i2、j1j1）j3 3i1i1、j2j2）快速排序算法舉例續(xù)二） 初始狀態(tài): 30 38 15 比較次數(shù) 第3趟 30 38 15 3i2、j1） 30， 15 38 小計(jì)：3 第4趟 70

18、60 49 2i1、j1） 49 60 70 2i1、j1） 小計(jì)：4k = 38ijk = 60ji快速排序算法舉例續(xù)三） 初始狀態(tài): 30 15 比較次數(shù) 第5趟 30 15 2i1、j1） 15 30 小計(jì)：2 最后狀態(tài)： 15 30 38 49 49 60 70 90 總計(jì)： 27 k = 30ij課堂練習(xí)nP233 3.9n數(shù)據(jù)數(shù)據(jù)2）4. 算法評價(jià)v分界點(diǎn)選取方法不同，排序效果差異很大；分界點(diǎn)選取方法不同，排序效果差異很大；v比較次數(shù)為比較次數(shù)為nlogn，即為：，即為：Onlogn）。）。v快速排序算法是不穩(wěn)定的。快速排序算法是不穩(wěn)定的。 三、簡單插入排序1.1.基本思想：基本思

19、想：將將n n個(gè)元素的數(shù)列分為已有序和無序兩個(gè)個(gè)元素的數(shù)列分為已有序和無序兩個(gè)部分。部分。 a1 a1，a2a2，a3a3，a4a4，,an,an a1(1) a1(1)，a2(1)a2(1)，a3(1)a3(1)，a4(1) ,an(1)a4(1) ,an(1) . . a1(n-1) a1(n-1)，a2(n-1) a2(n-1) ，, , an(n-1)an(n-1)有序有序 無序無序n每次處理：將無序數(shù)列的第一個(gè)元素與有序數(shù)列的元素從后往前逐個(gè)進(jìn)行比較,找出插入位置,將該元素插入到有序數(shù)列的合適位置中。n從前往后，若比ai小，則放在ai前面n從后往前，若比ai大，則放在ai后邊。2.插

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

21、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 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 ； fori=1；i=0 & t ai+1 ，則交換它們的位置。，則交換它們的位置。nStep3 重復(fù)上述步驟，

22、直到重復(fù)上述步驟，直到dK = 1。希爾排序例子d=5d=3插入排序插入排序最后以最后以1步長進(jìn)行排序步長進(jìn)行排序（此時(shí)就是簡單的插入排序了）（此時(shí)就是簡單的插入排序了） n希爾排序是基于插入排序的以下兩點(diǎn)性希爾排序是基于插入排序的以下兩點(diǎn)性質(zhì)而提出改進(jìn)方法的：質(zhì)而提出改進(jìn)方法的：n1插入排序在對幾乎已經(jīng)排好序的數(shù)據(jù)插入排序在對幾乎已經(jīng)排好序的數(shù)據(jù)操作時(shí)，操作時(shí)， 效率高，效率高， 即可以達(dá)到線性排序即可以達(dá)到線性排序的效率；的效率； n2但插入排序一般來說是低效的，但插入排序一般來說是低效的， 因因?yàn)椴迦肱判蛎看沃荒軐?shù)據(jù)移動一位。為插入排序每次只能將數(shù)據(jù)移動一位。 3. SHELL排序算法

23、(c+語言)template shellsort(T item,int n) int i,j,h; T t; h=n/2 ； while(h0) for(i=h;in;i+) /內(nèi)部為插入排序 t=itemi; j=i-h; while(t=0) itemj+h=itemj; j=j-h; itemj+h=t; h=h/2； 4. 算法評價(jià)n希爾排序算法比較次數(shù)約為希爾排序算法比較次數(shù)約為n1.5，因而，因而，其時(shí)間復(fù)雜度為其時(shí)間復(fù)雜度為O（ n1.5 ）。）。n該算法是不穩(wěn)定的。該算法是不穩(wěn)定的。希爾排序課堂練習(xí)n23 33 21 1 24 14 2 26 90 43nd=5 3 1五、簡單

24、選擇排序n1.1.基本思想：每次從待排序的記錄中選出基本思想：每次從待排序的記錄中選出關(guān)鍵字最小或最大的記錄，順序放在關(guān)鍵字最小或最大的記錄，順序放在已有序的記錄序列的最后或最前面，已有序的記錄序列的最后或最前面，直到全部數(shù)列有序。直到全部數(shù)列有序。n a1 a1，a2a2，a3a3，a4a4，,an,ann a1(1) a1(1)，a2(1)a2(1)，a3(1)a3(1)，a4(1),an(1)a4(1),an(1)n . .n a1(n-1) a1(n-1)，a2(n-1) a2(n-1) ，, an(n-, an(n-1) 1) 有序有序 無序無序2.選擇排序算法步驟nStep1 從原

25、始數(shù)列從原始數(shù)列a1,a2,a3,an開始進(jìn)行開始進(jìn)行排序，比較排序，比較n-1次，從中選出最小關(guān)鍵字，次，從中選出最小關(guān)鍵字，放在有序數(shù)列中，形成放在有序數(shù)列中，形成a1、a2,a3,an有序數(shù)列和無序數(shù)列兩部分，完成第有序數(shù)列和無序數(shù)列兩部分，完成第1趟排趟排序。序。nStep2 處理第處理第i趟排序時(shí)趟排序時(shí)(i=2,3,n)，從剩下，從剩下的的n-i+1個(gè)元素中找出最小關(guān)鍵字，放在有個(gè)元素中找出最小關(guān)鍵字，放在有序數(shù)列的后面。序數(shù)列的后面。nStep3 重復(fù)重復(fù)Step2，共進(jìn)行，共進(jìn)行n-1趟的選擇處理，趟的選擇處理，數(shù)列全部有序。數(shù)列全部有序。選擇排序舉例 設(shè)有數(shù)列 18，12，1

26、0，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;icount-1;+i) / n-1次循環(huán) k=i; / 無序部分第1個(gè)元素 t=itemi; / 及位置 for(j=i+1;jco

27、unt;+j) / 尋找最小值循環(huán) if(itemj= low(n/2)i = low(n/2)的結(jié)的結(jié)點(diǎn)都是葉子，因此以這些結(jié)點(diǎn)為根的子樹都已是堆。點(diǎn)都是葉子，因此以這些結(jié)點(diǎn)為根的子樹都已是堆。（1） 建堆次序1313一個(gè)結(jié)點(diǎn)的樹是堆一個(gè)結(jié)點(diǎn)的樹是堆05052323919124241616888842421313建大根堆建大根堆(c) (c) 只需依次將序號為只需依次將序號為low(n/2) low(n/2)-1low(n/2) low(n/2)-1， . .，1 1的結(jié)點(diǎn)作為根的子樹都調(diào)整為堆即可。的結(jié)點(diǎn)作為根的子樹都調(diào)整為堆即可。23239191242416160505888842421

28、313n/2n/2（1） 建堆次序(2) 建堆方法-“篩選法” 一: 如果Ri的左右子樹已是堆，這兩棵子樹的根分別是各自子樹中關(guān)鍵字最大的結(jié)點(diǎn)。23239191242416160505888842421313二二: :若根的關(guān)鍵字已是三者根、左孩子、右孩子若根的關(guān)鍵字已是三者根、左孩子、右孩子中的最大者，則無須做任何調(diào)整；否則必須將具中的最大者，則無須做任何調(diào)整；否則必須將具有最大關(guān)鍵字的孩子與根交換。有最大關(guān)鍵字的孩子與根交換。23239191242416160505888842421313三: 交換之后有可能導(dǎo)致新子樹不再是堆， 需要將新子樹調(diào)整為堆。如此逐層遞推下去，直到調(diào)整到樹葉為止。

29、42428888919113132424161605052323424288889191131324241616050523231717 ,1414考慮:如果最后一個(gè)節(jié)點(diǎn)不是14，而是12將如何？例子：關(guān)鍵字序列為例子：關(guān)鍵字序列為 42 42，1313，9191，2323， 24 24， 1616，0505，8888，n=8n=8，故從第四個(gè)結(jié)點(diǎn)開始調(diào)整，故從第四個(gè)結(jié)點(diǎn)開始調(diào)整424213139191232324241616050588884213912324160588424213139191888824241616050523234213918824160523不調(diào)整不調(diào)整4242131

30、39191888824241616050523234213918824160523424288889191232324241616050513134288912324160513919188884242232324241616050513139188422324160513建成的堆建成的堆424213139191888824241616050523234213918824160523m = 2m = 2hm = t = 13hm = t = 13j= 4 hj=88 j= 4 hj=88 hj+1 =24hj+1 =24j jm mSIFT(ET h, int n; int m) SIFT(E

31、T h, int n; int m) int j; ET t; t=hm; int j; ET t; t=hm; j=2 j=2 * * m; m; while (j = n) / while (j = n) /處理到葉子處理到葉子 if (jn)&(hj hj+1) if (jn)&(hj hj+1) j+; / j+; /兩顆子樹比較兩顆子樹比較 if (thj) /exchange if (thj) /exchange hm=hj; hm=hj; hj=t hj=t m=j; m=j; j=2 j=2 * * m; m; else break; else break; S

32、IFT(ET h, int n; int m) SIFT(ET h, int n; int m) int j; ET t; t=hm; int j; ET t; t=hm; j=2 j=2 * * m; m; while (j = n) / while (j = n) /處理到葉子處理到葉子 if (jn)&(hj hj+1) if (jn)&(hj hj+1) j+; / j+; /兩顆子樹比較兩顆子樹比較 if (thj) /exchange if (thj) /exchange hm=hj; hm=hj; hj=t hj=t m=j; m=j; j=2 j=2 * * m

33、; m; else break; else break; 42429191888824241616050523234288918824160523m = 4 t = 13m = 4 t = 13hm = 13hm = 13j= 8 hj=23 j= 8 hj=23 hn+1 =0hn+1 =01313j jm mSIFT(ET h, int n; int m) SIFT(ET h, int n; int m) int j; ET t; t=hm; int j; ET t; t=hm; j=2 j=2 * * m; m; while (j=n) / while (j=n) /處理到葉子處理到葉子

34、 if (jn)&(hj hj+1) if (jn)&(hj hj+1) j+; / j+; /兩顆子樹比較兩顆子樹比較 if (thj) /exchange if (t=0; i-) SIFT(R, n -1, i)q 由于建堆的結(jié)果把關(guān)鍵字最大的記錄選到了堆頂?shù)奈恢茫捎诮ǘ训慕Y(jié)果把關(guān)鍵字最大的記錄選到了堆頂?shù)奈恢茫判虻慕Y(jié)果應(yīng)是升序，如何解決而排序的結(jié)果應(yīng)是升序，如何解決? ?3.堆排序算法q應(yīng)該將應(yīng)該將R0R0和和Rn-1Rn-1交換，這就得到了第一趟排序的結(jié)交換，這就得到了第一趟排序的結(jié)果。果。q 第二趟排序的操作首先是將無序區(qū)第二趟排序的操作首先是將無序區(qū)R0R0

35、到到Rn-2Rn-2調(diào)整調(diào)整為堆。這時(shí)對于當(dāng)前堆來說，它的左右子樹仍然是堆，為堆。這時(shí)對于當(dāng)前堆來說，它的左右子樹仍然是堆，所以，可以調(diào)用所以，可以調(diào)用SIFTSIFT函數(shù)將函數(shù)將R0R0到到Rn-2Rn-2調(diào)整為大根堆，調(diào)整為大根堆，選出最大關(guān)鍵字放入堆頂，然后將堆頂與當(dāng)前無序區(qū)的選出最大關(guān)鍵字放入堆頂，然后將堆頂與當(dāng)前無序區(qū)的最后一個(gè)記錄最后一個(gè)記錄Rn-2Rn-2交換，如此反復(fù)進(jìn)行下去。交換，如此反復(fù)進(jìn)行下去。919188884242232324241616050513139188422324160513（a a初始堆初始堆R1R1到到R8R8舉例：舉例：1313888842422323

36、24241616050591911388422324160591（b b第一趟排序之后第一趟排序之后（c c重建的堆重建的堆R1R1到到R7R7888824244242232313131616050591918824422313160591050524244242232313131616888891910524422313168891（d d第二趟排序之后第二趟排序之后（e e重建的堆重建的堆R1R1到到R6R6424224241616232313130505888891914224162313058891（f f第三趟排序之后第三趟排序之后05052424161623231313424288

37、8891910524162313428891（g g重建的堆重建的堆R1R1到到R5R5242423231616050513134242888891912423160513428891（h h第四趟排序之后第四趟排序之后131323231616050524244242888891911323160524428891（i i重建的堆重建的堆R1R1到到R4R4232313131616050524244242888891912313160524428891（j j第五趟排序之后第五趟排序之后050513131616232324244242888891910513162324428891（k k重建

38、的堆重建的堆R1R1到到R3R3161613130505232324244242888891911613052324428891（l l第六趟排序之后第六趟排序之后050513131616232324244242888891910513162324428891（m m重建的堆重建的堆R1R1到到R2R2131305051616232324244242888891911305162324428891（n n第七趟排序之后第七趟排序之后050513131616232324244242888891910513162324428891HEAPSORT(ET p)HEAPSORT(ET p) int i

39、; ET t; int i; ET t; for (i=n/2 -1;i=1;i-) for (i=n/2 -1;i=1;i-) sift(p, n-1, i); sift(p, n-1, i); for (i=n-1;i=1;i-) for (i=n-1;i=1;i-) t=p0; p0=pi; t=p0; p0=pi; pi=t; pi=t; sift(p, i-1, 0); sift(p, i-1, 0); 4.堆排序的時(shí)間復(fù)雜度堆排序的時(shí)間復(fù)雜性為O(nlog2n) 空間復(fù)雜性為 O(1)堆排序是不穩(wěn)定的排序方法。堆排序課堂練習(xí)n23 33 21 1 24 14 2 26 90 43n

40、1先建大根堆寫出過程）先建大根堆寫出過程）n2排序！排序！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)排序的。歸并排序就是利用上述歸并操作實(shí)現(xiàn)排序的。(1)(1)將待排序列將待排序列R1R1到到RnRn看成看成n n個(gè)長度為個(gè)長度為1 1的有序子序的有序子序列，把這些子序列兩兩歸并，便得到列，把這些子序列兩兩歸并，便得到high(n/2)high(n/2)個(gè)有序個(gè)有序的子序列。的子序列。(2)(2)然后再把這然后再把這high(n/2)hi

41、gh(n/2)個(gè)有序的子序列兩兩歸并，個(gè)有序的子序列兩兩歸并，如此反復(fù)，直到最后得到一個(gè)長度為如此反復(fù)，直到最后得到一個(gè)長度為n n的有序序列。的有序序列。(3)(3)上述每次歸并操作，都是將兩個(gè)子序列歸并為一個(gè)上述每次歸并操作，都是將兩個(gè)子序列歸并為一個(gè)子序列，這就是子序列，這就是“二路歸并二路歸并”，類似地還可以有，類似地還可以有“三三路歸并或路歸并或“多路歸并多路歸并”。算法評價(jià)n空間復(fù)雜度為空間復(fù)雜度為O O（ n n ），），n 用輔助空間用輔助空間L1L1、L2L2、（、（SwapSwap）n時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為O Onlognnlogn）n2-2-路歸并排序算法是穩(wěn)定的。路歸

42、并排序算法是穩(wěn)定的。 八、基數(shù)排序 q多關(guān)鍵字排序技術(shù)：多關(guān)鍵字（多關(guān)鍵字排序技術(shù)：多關(guān)鍵字（ K1 ,K2, K1 ,K2, Kt Kt ）; ; 例如：關(guān)鍵字例如：關(guān)鍵字 K1 K1 小的結(jié)點(diǎn)排在前面。如關(guān)小的結(jié)點(diǎn)排在前面。如關(guān)鍵字鍵字 K1 K1相同，則比較關(guān)鍵字相同，則比較關(guān)鍵字 K2 K2 ，關(guān)鍵字，關(guān)鍵字 K2 K2 小的小的結(jié)點(diǎn)排在前面，依次類推結(jié)點(diǎn)排在前面，依次類推 1.舉例p 假定給定的是假定給定的是 t = 2 位十進(jìn)制數(shù)，存放在數(shù)組位十進(jìn)制數(shù)，存放在數(shù)組 B 之中。之中。現(xiàn)要求通過基數(shù)排序法將其排序。現(xiàn)要求通過基數(shù)排序法將其排序。p 設(shè)置十個(gè)口袋，因十進(jìn)制數(shù)分別有數(shù)字：設(shè)

43、置十個(gè)口袋，因十進(jìn)制數(shù)分別有數(shù)字：0，1，2，9 ，分別用，分別用 B0、B1、B2、B9 進(jìn)行標(biāo)識。進(jìn)行標(biāo)識。p 執(zhí)行執(zhí)行 j = 1t (這里這里t = 2 )次循環(huán)，每次進(jìn)行一次分配次循環(huán)，每次進(jìn)行一次分配動作，一次收集動作。動作，一次收集動作。p 將右起第將右起第 j 位數(shù)字相同的數(shù)放入同一口袋。比如數(shù)字位數(shù)字相同的數(shù)放入同一口袋。比如數(shù)字為為 1 者，則放入口袋者，則放入口袋B1，余類推，余類推 搜集：按搜集：按 B0、B1、B2、 B9 的順序進(jìn)行收集。的順序進(jìn)行收集。基數(shù)排序舉例 e.g: B = 5 、2、9、7、18、17、52 用基數(shù)排序法進(jìn)行排序。用基數(shù)排序法進(jìn)行排序。

44、B = 5、2、9、7、18、17、52 B0B1B2B3B4B5B6B7B8B9口袋口袋根據(jù)根據(jù) 所指向的所指向的 數(shù)，進(jìn)行分配動作，數(shù)，進(jìn)行分配動作，將其分配到相應(yīng)的口將其分配到相應(yīng)的口 袋。袋。基數(shù)排序舉例 e.g: B = 5 、2、9、7、18、17、52 用基數(shù)排序法進(jìn)行排序。用基數(shù)排序法進(jìn)行排序。 B = 5、2、9、7、18、17、52 B0B1B2B3B4B5B6B7B8B9口袋口袋根據(jù)根據(jù) 所指向的所指向的 數(shù)，進(jìn)行分配動作，數(shù)，進(jìn)行分配動作，將其分配到相應(yīng)的口將其分配到相應(yīng)的口 袋。袋。5基數(shù)排序舉例 e.g: B = 5 、2、9、7、18、17、52 用基數(shù)排序法進(jìn)行

45、排序。用基數(shù)排序法進(jìn)行排序。 B = 5、2、9、7、18、17、52 B0B1B2B3B4B5B6B7B8B9口袋口袋根據(jù)根據(jù) 所指向的所指向的 數(shù)，進(jìn)行分配動作，數(shù)，進(jìn)行分配動作，將其分配到相應(yīng)的口將其分配到相應(yīng)的口 袋。袋。5基數(shù)排序舉例 e.g: B = 5 、2、9、7、18、17、52 用基數(shù)排序法進(jìn)行排序。用基數(shù)排序法進(jìn)行排序。 B = 5、2、9、7、18、17、52 B0B1B2B3B4B5B6B7B8B9口袋口袋根據(jù)根據(jù) 所指向的所指向的 數(shù)，進(jìn)行分配動作，數(shù)，進(jìn)行分配動作，將其分配到相應(yīng)的口將其分配到相應(yīng)的口 袋。袋。52基數(shù)排序舉例 e.g: B = 5 、2、9、7、

46、18、17、52 用基數(shù)排序法進(jìn)行排序。用基數(shù)排序法進(jìn)行排序。 B = 5、2、9、7、18、17、52 B0B1B2B3B4B5B6B7B8B9口袋口袋根據(jù)根據(jù) 所指向的所指向的 數(shù)，進(jìn)行分配動作，數(shù)，進(jìn)行分配動作，將其分配到相應(yīng)的口將其分配到相應(yīng)的口 袋。袋。52基數(shù)排序舉例 e.g: B = 5 、2、9、7、18、17、52 用基數(shù)排序法進(jìn)行排序。用基數(shù)排序法進(jìn)行排序。 B = 5、2、9、7、18、17、52 B0B1B2B3B4B5B6B7B8B9口袋口袋根據(jù)根據(jù) 所指向的所指向的 數(shù)，進(jìn)行分配動作，數(shù)，進(jìn)行分配動作，將其分配到相應(yīng)的口將其分配到相應(yīng)的口 袋。袋。529基數(shù)排序舉例

47、 e.g: B = 5 、2、9、7、18、17、52 用基數(shù)排序法進(jìn)行排序。用基數(shù)排序法進(jìn)行排序。 B = 5、2、9、7、18、17、52 B0B1B2B3B4B5B6B7B8B9口袋口袋根據(jù)根據(jù) 所指向的所指向的 數(shù)，進(jìn)行分配動作，數(shù)，進(jìn)行分配動作，將其分配到相應(yīng)的口將其分配到相應(yīng)的口 袋。袋。529基數(shù)排序舉例 e.g: B = 5 、2、9、7、18、17、52 用基數(shù)排序法進(jìn)行排序。用基數(shù)排序法進(jìn)行排序。 B = 5、2、9、7、18、17、52 B0B1B2B3B4B5B6B7B8B9口袋口袋根據(jù)根據(jù) 所指向的所指向的 數(shù)，進(jìn)行分配動作，數(shù)，進(jìn)行分配動作，將其分配到相應(yīng)的口將其分

48、配到相應(yīng)的口 袋。袋。5297基數(shù)排序舉例 e.g: B = 5 、2、9、7、18、17、52 用基數(shù)排序法進(jìn)行排序。用基數(shù)排序法進(jìn)行排序。 B = 5、2、9、7、18、17、52 B0B1B2B3B4B5B6B7B8B9口袋口袋根據(jù)根據(jù) 所指向的所指向的 數(shù)，進(jìn)行分配動作，數(shù)，進(jìn)行分配動作，將其分配到相應(yīng)的口將其分配到相應(yīng)的口 袋。袋。5297基數(shù)排序舉例 e.g: B = 5 、2、9、7、18、17、52 用基數(shù)排序法進(jìn)行排序。用基數(shù)排序法進(jìn)行排序。 B = 5、2、9、7、18、17、52 B0B1B2B3B4B5B6B7B8B9口袋口袋根據(jù)根據(jù) 所指向的所指向的 數(shù)，進(jìn)行分配動作

49、，數(shù)，進(jìn)行分配動作，將其分配到相應(yīng)的口將其分配到相應(yīng)的口 袋。袋。529718基數(shù)排序舉例 e.g: B = 5 、2、9、7、18、17、52 用基數(shù)排序法進(jìn)行排序。用基數(shù)排序法進(jìn)行排序。 B = 5、2、9、7、18、17、52 B0B1B2B3B4B5B6B7B8B9口袋口袋根據(jù)根據(jù) 所指向的所指向的 數(shù)，進(jìn)行分配動作，數(shù)，進(jìn)行分配動作，將其分配到相應(yīng)的口將其分配到相應(yīng)的口 袋。袋。529718基數(shù)排序舉例 e.g: B = 5 、2、9、7、18、17、52 用基數(shù)排序法進(jìn)行排序。用基數(shù)排序法進(jìn)行排序。 B = 5、2、9、7、18、17、52 B0B1B2B3B4B5B6B7B8B9

50、口袋口袋根據(jù)根據(jù) 所指向的所指向的 數(shù)，進(jìn)行分配動作，數(shù)，進(jìn)行分配動作，將其分配到相應(yīng)的口將其分配到相應(yīng)的口 袋。袋。52971817基數(shù)排序舉例 e.g: B = 5 、2、9、7、18、17、52 用基數(shù)排序法進(jìn)行排序。用基數(shù)排序法進(jìn)行排序。 B = 5、2、9、7、18、17、52 B0B1B2B3B4B5B6B7B8B9口袋口袋根據(jù)根據(jù) 所指向的所指向的 數(shù)，進(jìn)行分配動作，數(shù)，進(jìn)行分配動作，將其分配到相應(yīng)的口將其分配到相應(yīng)的口 袋。袋。52971817基數(shù)排序舉例 e.g: B = 5 、2、9、7、18、17、52 用基數(shù)排序法進(jìn)行排序。用基數(shù)排序法進(jìn)行排序。 B = 5、2、9、7

51、、18、17、52 B0B1B2B3B4B5B6B7B8B9口袋口袋根據(jù)根據(jù) 所指向的所指向的 數(shù)，進(jìn)行分配動作，數(shù)，進(jìn)行分配動作，將其分配到相應(yīng)的口將其分配到相應(yīng)的口 袋。袋。5297181752基數(shù)排序舉例 e.g: B = 5 、2、9、7、18、17、52 用基數(shù)排序法進(jìn)行排序。用基數(shù)排序法進(jìn)行排序。 B = 5、2、9、7、18、17、52 B0B1B2B3B4B5B6B7B8B9口袋口袋分配完畢，依照分配完畢，依照 箭頭所指的方向進(jìn)行箭頭所指的方向進(jìn)行 收集動作。注意：收收集動作。注意：收集后的序列已經(jīng)按照集后的序列已經(jīng)按照右起第一位個(gè)位數(shù)右起第一位個(gè)位數(shù)字排好序了。字排好序了。5

52、297181752收集后的序列：收集后的序列：2、52、5、7、17、18、9、基數(shù)排序舉例 e.g: B = 5 、2、9、7、18、17、52 用基數(shù)排序法進(jìn)行排序。用基數(shù)排序法進(jìn)行排序。 B = 2、52、5、7、17、18、9 （第一次收集的結(jié)果）（第一次收集的結(jié)果）B0B1B2B3B4B5B6B7B8B9口袋口袋根據(jù)根據(jù) 所指向的所指向的 數(shù)，進(jìn)行分配動作，數(shù)，進(jìn)行分配動作，將其分配到相應(yīng)的口將其分配到相應(yīng)的口 袋。和第一次不同，袋。和第一次不同，這次根據(jù)右起第二位這次根據(jù)右起第二位數(shù)字十位數(shù)字進(jìn)數(shù)字十位數(shù)字進(jìn)分配。分配。基數(shù)排序舉例 e.g: B = 5 、2、9、7、18、17、

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

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

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

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

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

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

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

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