數(shù)據(jù)結(jié)構(gòu)之樹和圖算法ppt課件

1、第9章 排序設(shè)設(shè) n 個記錄的序列為個記錄的序列為 R1 , R2 , R3 , . . . , Rn 其相應(yīng)的關(guān)鍵字序列為其相應(yīng)的關(guān)鍵字序列為 K1 , K2 , K3 , . . . , Kn 若規(guī)定若規(guī)定 1 , 2 , 3 , . . . , n 的一個排列的一個排列 p1 , p2 , p3 , . . . , pn ，使得相應(yīng)的關(guān)鍵字滿足如下非遞減關(guān)系使得相應(yīng)的關(guān)鍵字滿足如下非遞減關(guān)系:Kp Kp Kp . . . Kp123n則原序列變?yōu)橐粋€按關(guān)鍵字有序的序列則原序列變?yōu)橐粋€按關(guān)鍵字有序的序列:Rp , Rp , Rp , . . . , Rp123n 此操作過程稱為排序。此操作

2、過程稱為排序。第9章 排序假設(shè)假設(shè) Ki = Kj ，且排序前序列中，且排序前序列中 Ri 領(lǐng)先于領(lǐng)先于 Rj ；若在排序后的序列中若在排序后的序列中 Ri 仍領(lǐng)先于仍領(lǐng)先于 Rj ，則稱排序方法是，則稱排序方法是穩(wěn)定的。穩(wěn)定的。若在排序后的序列中若在排序后的序列中 Rj 仍領(lǐng)先于仍領(lǐng)先于 Ri ，則稱排序方法是，則稱排序方法是不穩(wěn)定的。不穩(wěn)定的。例，序列例，序列 3 15 8 8 6 9若排序后得若排序后得 3 6 8 8 9 15穩(wěn)定的穩(wěn)定的若排序后得若排序后得 3 6 8 8 9 15不穩(wěn)定的不穩(wěn)定的第9章 排序內(nèi)部排序內(nèi)部排序: 指的是待排序記錄存放在計算機隨機存儲指的是待排序記錄存放

3、在計算機隨機存儲器中進行的排序過程。器中進行的排序過程。外部排序外部排序: 指的是待排序記錄的數(shù)量很大，以致內(nèi)存指的是待排序記錄的數(shù)量很大，以致內(nèi)存一次不能容納全部記錄，在排序過程中尚需對外存進一次不能容納全部記錄，在排序過程中尚需對外存進行訪問的排序過程。行訪問的排序過程。第9章 排序排序過程主要是對記錄的排序碼進行比較和記錄的移動過程。因此排序的時間復(fù)雜性可以算法執(zhí)行中的數(shù)據(jù)比較次數(shù)及數(shù)據(jù)移動次數(shù)來衡量。當(dāng)一種排序方法使排序過程在最壞或平均情況下所進行的比較和移動次數(shù)越少，則認(rèn)為該方法的時間復(fù)雜性就越好，分析一種排序方法，不僅要分析它的時間復(fù)雜性，而且要分析它的空間復(fù)雜性、穩(wěn)定性和簡單性等

4、。第9章 排序按照排序過程中所依據(jù)的原則的不同可以分類為按照排序過程中所依據(jù)的原則的不同可以分類為: 插入排序插入排序 交換排序交換排序(快速排序快速排序) 選擇排序選擇排序 歸并排序歸并排序 基數(shù)排序基數(shù)排序 二叉排序樹排序二叉排序樹排序第9章 排序思想思想: 利用有序表的插入操作進行排序利用有序表的插入操作進行排序有序表的插入有序表的插入: 將一個記錄插入到已排好序的有序表中，將一個記錄插入到已排好序的有序表中，從而得到一個新的有序表。從而得到一個新的有序表。例，序列例，序列 13 27 38 65 76 97 插入插入 4913 27 38 49 65 76 97第9章 排序例，序列例，

5、序列 49 38 65 97 76 13 27 初始，初始，S = 49 ； 38 49 初始，令第初始，令第 1 個元素作為初始有序表；個元素作為初始有序表；依次插入第依次插入第 2 , 3 , , k 個元素構(gòu)造新的有序表；個元素構(gòu)造新的有序表；直至最后一個元素；直至最后一個元素； 38 49 65 38 49 65 97 38 49 65 76 97 13 38 49 65 76 97 13 27 38 49 65 76 97 直接插入排序算法主要應(yīng)用比較和移動兩種操作。直接插入排序算法主要應(yīng)用比較和移動兩種操作。第9章 排序void insertsort(ElemType R,int

6、n)/待排序元素用一個數(shù)組R表示，數(shù)組有n個元素 for ( int i=1; i=0)& (tempRj) Rj+1=Rj; j-; / 順序比較和移動 Rj+1=temp;第9章 排序 直接插入排序的效率分析直接插入排序的效率分析從空間來看，它只需要一個元素的輔助空間，用于元素的位置交換。從時間分析，首先外層循環(huán)要進行n-1次插入，每次插入最少比較一次正序），移動兩次；最多比較i次，移動i2次逆序）（i=1，2，n-1）。Cmin=n-1 M min=2n-1）Cmax=1+2+n-1=（n2-n）/2 M max=3+4+n+1=（n2+3n-4）/2Cave=（n2+n-2）/4 M

7、max=（n2+7n-8）/4因此，直接插入排序的時間復(fù)雜度為On2）。直接插入算法的元素移動是順序的，該方法是穩(wěn)定的。第9章 排序由于直接插入排序算法利用了有序表的插入操作，由于直接插入排序算法利用了有序表的插入操作，故順序查找操作可以替換為折半查找操作。故順序查找操作可以替換為折半查找操作。例，序列例，序列 49 38 65 97 76 13 27 設(shè)已形成有序表設(shè)已形成有序表 38 49 65 97 76 插入元素插入元素 13第9章 排序算法:void BinaryInsertSort(ElemType R,int n) for(int i=1; in; i+) /共進行n-1次插入

8、int left=0,right=i-1;ElemType temp=Ri; while(left=right) int middle=(left+right)/2; /取中點 if(temp=left;j-) Rj+1=Rj; /元素后移空出插入位 Rleft=temp; 第9章 排序二分插入算法與直接插入算法相比，需要輔助空間與直接插入排序基本一致；時間上，前者的比較次數(shù)比直接插入查找的最壞情況好，最好的情況壞，兩種方法的元素的移動次數(shù)相同，因此二分插入排序的時間復(fù)雜度仍為O(n2)。二分插入算法與直接插入算法的元素移動一樣是順序的，因此該方法也是穩(wěn)定的。第9章 排序分析直接插入排序分析直

9、接插入排序1. 若待排序記錄序列按關(guān)鍵字基本有序，則排序效若待排序記錄序列按關(guān)鍵字基本有序，則排序效率可大大提高；率可大大提高；2. 待排序記錄總數(shù)越少，排序效率越高；待排序記錄總數(shù)越少，排序效率越高；第9章 排序思想思想: 先將待排序記錄序列分割成為若干子序列分別進行直接插入排序；先將待排序記錄序列分割成為若干子序列分別進行直接插入排序；待整個序列中的記錄基本有序后，再全體進行一次直接插入排序。待整個序列中的記錄基本有序后，再全體進行一次直接插入排序。例，序列例，序列 49 38 65 97 76 13 27 48 55 4 19 第一趟排序第一趟排序49 13 1938 2765 4897

10、 5576 413 19 4927 3848 6555 974 76第9章 排序第二趟排序第二趟排序13 19 4927 3848 6555 974 7613 55 38 7627 4 65 4948 19 9713 38 55 764 27 49 6519 48 97第三趟排序第三趟排序4 13 19 27 38 48 49 55 65 76 97第9章 排序第9章 排序希爾排序的時間復(fù)雜性在Onlog2n和On2 ）之間，大致為On1.3）。第9章 排序思想思想: 通過不斷比較相鄰元素大小，進行交換來實現(xiàn)排序。通過不斷比較相鄰元素大小，進行交換來實現(xiàn)排序。首先將第一個元素與第二個元素比較大

11、小，若為逆序，則交換；首先將第一個元素與第二個元素比較大小，若為逆序，則交換；然后比較第二個元素與第三個元素的大小，若為逆序，則交換；然后比較第二個元素與第三個元素的大小，若為逆序，則交換；. . .直至比較第直至比較第 n-1 個元素與第個元素與第 n 個元素的大小，若為逆序，則交換；個元素的大小，若為逆序，則交換；第一趟排序第一趟排序:結(jié)果結(jié)果:關(guān)鍵字最大的記錄被交換至最后一個元素位置上。關(guān)鍵字最大的記錄被交換至最后一個元素位置上。第9章 排序例，序列例，序列 49 38 76 13 2749 38 76 13 2738 49 13 27 38 4913 7627 76初始初始第一趟排序后

12、第一趟排序后最大值最大值13 4927 49次大值次大值第二趟排序后第二趟排序后38 13 2713 2713 38 27 38第三趟排序后第三趟排序后第四趟排序后第四趟排序后第9章 排序冒泡排序的算法實現(xiàn)。冒泡排序的算法實現(xiàn)。void Bubblesort(ElemType R,int n) int flag=1; /當(dāng)當(dāng)flag為為0則停止排序則停止排序 for (int i=1; i=i; j-) if (RjRj-1) /發(fā)生逆序發(fā)生逆序 ElemType t=Rj;Rj=Rj-1;Rj-1=t;flag=1; /交換，并標(biāo)記發(fā)生了交換交換，并標(biāo)記發(fā)生了交換 if(flag=0)ret

13、urn; 第9章 排序冒泡排序的效率分析冒泡排序的效率分析從冒泡排序的算法可以看出，若待排序的元素為正序，從冒泡排序的算法可以看出，若待排序的元素為正序，則只需進行一趟排序，比較次數(shù)為則只需進行一趟排序，比較次數(shù)為n-1次，移動元次，移動元素次數(shù)為素次數(shù)為0；若待排序的元素為逆序，則需進行；若待排序的元素為逆序，則需進行n-1趟趟排序，比較次數(shù)為排序，比較次數(shù)為(n2-n)/2，移動次數(shù)為，移動次數(shù)為3(n2-n )/2，因，因此冒泡排序算法的時間復(fù)雜度為此冒泡排序算法的時間復(fù)雜度為On2）。由于其中）。由于其中的元素移動較多，所以屬于內(nèi)排序中速度較慢的一種。的元素移動較多，所以屬于內(nèi)排序中速

14、度較慢的一種。因為冒泡排序算法只進行元素間的順序移動，所以是因為冒泡排序算法只進行元素間的順序移動，所以是一個穩(wěn)定的算法。一個穩(wěn)定的算法。第9章 排序冒泡排序的一種改進算法。冒泡排序的一種改進算法。思想思想:以首記錄作為軸記錄，從前、后雙向掃描序列，通過交換，實以首記錄作為軸記錄，從前、后雙向掃描序列，通過交換，實現(xiàn)大值記錄后移，小值記錄前移，最終將軸記錄安置在一個適現(xiàn)大值記錄后移，小值記錄前移，最終將軸記錄安置在一個適當(dāng)?shù)奈恢?。?dāng)?shù)奈恢谩?小值記錄在前、大值記錄在后小值記錄在前、大值記錄在后)軸記錄將原序列分割成兩部分，依次對前后兩部分重新設(shè)定軸軸記錄將原序列分割成兩部分，依次對前后兩部分重

15、新設(shè)定軸記錄，繼而分別再進行快速排序。記錄，繼而分別再進行快速排序。直至整個序列有序。直至整個序列有序。第9章 排序 快速排序?qū)嵗齨快排序算法思想第9章 排序|快排序-分割過程|快排序是一個分治算法也是第一個）|快排序的關(guān)鍵過程是每次遞歸的分割過程|分割問題描述：對一個序列，取它的一個元素作為軸，把所有小于軸的元素放在它的左邊，大于它的元素放在它的右邊|分割算法：|用臨時變量對軸備份|取兩個指針low和high，它們的初始值就是序列的兩端下標(biāo)，在整個過程中保證low不大于high|移動兩個指針|首先從high所指的位置向左搜索，找到第一個小于軸的元素, 把這個元素放在low的位置|再從low開

16、始向右，找到第一個大于軸的元素，把它放在high的位置第9章 排序|快排序-分割過程|分割算法：|重復(fù)上述過程，直到low=high，|把軸放在low所指的位置|這樣所有大于軸的元素被放在右邊，所有小于軸的元素被放在左邊第9章 排序|快排序-分割過程第9章 排序|快排序-分割過程|int Partition(T Array, int low, int high)| T pivot = Arraylow;|/ while(low high) /在作為快排序的子程序時不用| while(low = pivot)|high -;| Arraylow = Arrayhigh;| while(low h

17、igh & Arraylow = pivot)|low+;| Arrayhigh = Arraylow;| / /在作為快排序的子程序時不用| Arraylow = pivot;| return low;|第9章 排序|快排序-算法|快排序算法是個遞歸地對序列進行分割的過程，遞歸終止的條件是最終序列長度為1第9章 排序|快排序-算法|void QuickSort(T Array, int low, int high)|int PivotLocation;| if(low high)| PivotLocation = Partition(Array, low, high);| QuickSort

18、(Array, low, PivotLocation-1);| QuickSort(Array, PivotLocation+1, high);| |第9章 排序3快速排序的效率分析快速排序的效率分析若快速排序出現(xiàn)最好的情形左、右子區(qū)間的長度大致相 等 ） ， 則 結(jié) 點 數(shù) n 與 二 叉 樹 深 度 h 應(yīng) 滿 足log2nhlog2n+1 ，所以總的比較次數(shù)不會超過(n+1) log2n。因此，快速排序的最好時間復(fù)雜度應(yīng)為Onlog2n）。而且在理論上已經(jīng)證明，快速排序的平均時間復(fù)雜度也為Onlog2n）。若快速排序出現(xiàn)最壞的情形每次能劃分成兩個子區(qū)間，但其中一個是空），則這時得到的二叉

19、樹是一棵單分枝樹，得到的非空子區(qū)間包含有n-i個(i代表二叉樹的層數(shù)1in元素，每層劃分需要比較n-i+2次，所以總的比較次數(shù)為n2+3n-4）/2。因此，快速排序的最壞時間復(fù)雜度為O(n2)?？焖倥判蛩加玫妮o助空間為棧的深度，故最好的空間復(fù)雜度為Olog2n），最壞的空間復(fù)雜度為O(n)?？焖倥判蚴且环N不穩(wěn)定的排序方法。 第9章 排序思想思想: 每一趟都選出一個最大或最小的元素，并放在每一趟都選出一個最大或最小的元素，并放在合適當(dāng)?shù)奈恢谩：线m當(dāng)?shù)奈恢谩?簡單選擇排序簡單選擇排序 樹形選擇排序樹形選擇排序 堆排序堆排序第9章 排序思想思想: 第第 1 趟選擇趟選擇: 從從 1n 個記錄中選擇

20、關(guān)鍵字最小的記錄，并和第個記錄中選擇關(guān)鍵字最小的記錄，并和第 1 個個記錄交換。記錄交換。第第 2 趟選擇趟選擇: 從從 2n 個記錄中選擇關(guān)鍵字最小的記錄，并和第個記錄中選擇關(guān)鍵字最小的記錄，并和第 2 個個記錄交換。記錄交換。第第n-1趟選擇趟選擇:從從 n-1n 個記錄中選擇關(guān)鍵字最小的記錄，并和第個記錄中選擇關(guān)鍵字最小的記錄，并和第 n-1 個記錄交換。個記錄交換。. . .第9章 排序例，序列例，序列 49 38 97 65 76第第 1 趟選擇趟選擇:min38 49 97 65 76第第 2 趟選擇趟選擇:min38 49 97 65 76第第 3 趟選擇趟選擇:min38 49

21、 65 97 76第第 4 趟選擇趟選擇:min38 49 65 76 97第9章 排序第9章 排序選擇排序的主要操作是進行關(guān)鍵字間的比較。選擇排序的主要操作是進行關(guān)鍵字間的比較。在在 n 個關(guān)鍵字中選出最小值，至少需要個關(guān)鍵字中選出最小值，至少需要 n-1 次比較。次比較。在剩余的在剩余的 n-1 個關(guān)鍵字中選出最小值，至少需要個關(guān)鍵字中選出最小值，至少需要 n-2 次比較？次比較？如果能利用前如果能利用前 n-1 次比較所得信息，可以減少后面選擇次比較所得信息，可以減少后面選擇的比較次數(shù)。的比較次數(shù)。體育比賽中的錦標(biāo)賽體育比賽中的錦標(biāo)賽:第9章 排序例，例，8 名運動員要決出名運動員要決出

22、 冠、亞、季軍。冠、亞、季軍。按簡單選擇排序需要比賽按簡單選擇排序需要比賽 7+6+5 = 18 場。場。若能夠利用以前的比賽結(jié)果，比賽場次實際可以減少為若能夠利用以前的比賽結(jié)果，比賽場次實際可以減少為 11 場。場。前提前提: 假設(shè)假設(shè) 甲甲 勝勝 乙乙 ，乙，乙 勝勝 丙丙 ，那么，那么 甲甲 必能勝必能勝 丙丙 。ZhaoChaLiuBaoDiaoYangXueWangBaoBaoDiaoChaBaoDiaoWang冠軍冠軍第9章 排序如何求如何求 亞軍？亞軍？ZhaoChaLiuDiaoYangXueWangChaDiaoCha亞軍亞軍可以利用前面的比賽結(jié)果！可以利用前面的比賽結(jié)果！C

23、haLiuDiaoWang第9章 排序如何求如何求 季軍？季軍？ZhaoLiuDiaoYangXueWangLiuDiaoDiao季軍季軍同樣可以利用前面的比賽結(jié)果！同樣可以利用前面的比賽結(jié)果！LiuDiaoWangZhao第9章 排序又稱錦標(biāo)賽排序，是一種按照錦標(biāo)賽的思想進行選擇排序的方又稱錦標(biāo)賽排序，是一種按照錦標(biāo)賽的思想進行選擇排序的方法。法。例，序列例，序列 49 38 65 97 76 13 27 50第一趟選擇第一趟選擇133813493865977613275038651327最小值最小值第9章 排序第二趟選擇第二趟選擇2738274938659776275038657627次小

24、值次小值第三趟選擇第三趟選擇38385049386597765038657650次次小值次次小值493865977613275049386597762750缺陷缺陷: 需要需要大量輔助存大量輔助存儲空間儲空間第9章 排序堆堆: 一棵完全二叉樹，任一個非終端結(jié)點的值均小于等一棵完全二叉樹，任一個非終端結(jié)點的值均小于等于于(或大于等于或大于等于)其左、右兒子結(jié)點的值。其左、右兒子結(jié)點的值。例，例，1285473053362491963811 98324根結(jié)點為最小值根結(jié)點為最小值根結(jié)點為最大值根結(jié)點為最大值第9章 排序2. 把這棵普通的完全二叉樹改造成堆，便可獲取最小值把這棵普通的完全二叉樹改造成

25、堆，便可獲取最小值 ；思想思想:3. 輸出最小值輸出最小值 ；4. 刪除根結(jié)點，繼續(xù)改造剩余樹成堆，便可獲取次小值刪除根結(jié)點，繼續(xù)改造剩余樹成堆，便可獲取次小值 ；5. 輸出次小值輸出次小值 ；6. 重復(fù)改造，輸出次次小值、次次次小值，直至所有結(jié)點均重復(fù)改造，輸出次次小值、次次次小值，直至所有結(jié)點均輸出，便得到一個排序輸出，便得到一個排序 。1. 將序列構(gòu)造成一棵完全二叉樹將序列構(gòu)造成一棵完全二叉樹 ；第9章 排序例，序列例，序列 49 38 65 97 76 13 27 501. 按順序依次構(gòu)造成完全二叉樹的結(jié)點；按順序依次構(gòu)造成完全二叉樹的結(jié)點；49386597761327502. 把完全

26、二叉樹改造成堆；把完全二叉樹改造成堆；從下向上，父子交換；從下向上，父子交換；50971365134949273. 取得最小值取得最小值 134. 刪除刪除 13 ，重新改造成新堆；，重新改造成新堆；1397279797495. 取得次小值取得次小值 27；6. 刪除刪除 27 ，重新改造成新堆；，重新改造成新堆；9727973897507. 取得次次小值取得次次小值 38；第9章 排序|歸并-合并兩個有序的序列|假設(shè)有兩個已排序好的序列A長度為n1），B長度為n2），將它們合并為一個有序的序列C長度為n=n1+n2)|方法很簡單：把A，B兩個序列的最小元素進行比較，把其中較小的元素作為C的第

27、一個元素；在A，B剩余的元素中繼續(xù)挑最小的元素進行比較，確定C的第二個元素，依次類推，就可以完成對A和B的歸并， 其復(fù)雜度為O(n)第9章 排序|歸并-合并兩個有序的序列第9章 排序|歸并-合并兩個有序的序列|void merge(T A, int Alen, T B, int Blen, T C)| int i=0,j=0,k=0;| while(i Alen & j Blen)| if(Ai Bj)| Ck+ = Ai+; | else| Ck+ = Bj+;|while(i Alen)|Ck+ = Ai+;| while(j Blen)|Ck+ = Bj+;|第9章 排序|歸并-合并一個

28、序列中的兩個有序的數(shù)據(jù)段|void merge(T A, int l, int m, int h)| int i=l,j=m+1,k=0; | T *C = new Th-l+1;| while(i = m & j = h)| if(Ai Aj) Ck+ = Ai+; | else Ck+ = Aj+; |while(i =m) Ck+ = Ai+;| while(j =h) Ck+ = Bj+;| for(k=0;kb和ab), |如果以每次比較作為節(jié)點，則每個以比較為基礎(chǔ)的排序算法都可以用一個二叉樹來表示，其中一個中間節(jié)點表示一次比較，葉子節(jié)點表示排序的一種結(jié)果，這樣的二叉樹稱為判定樹或決

29、策樹|舉例：比如有一個序列a, b, c(a,b,c互不相等） ，下列算法：|先比較a和b, 再比較a和c，最后比較b和c| 可以用下面的判定樹表示|第9章 排序|以比較為基礎(chǔ)的排序算法的下界第9章 排序|以比較為基礎(chǔ)的排序算法的下界|假設(shè)輸入為a,b,c, acb, 則算法執(zhí)行經(jīng)過的路線為(ab)(ac)(bc)，需要3次比較|假設(shè)輸入為a,b,c, bac, 則算法執(zhí)行經(jīng)過的路線為(ab)(ac) 需要2次比較|任何以比較為基礎(chǔ)的排序算法都可以表示為一棵決策樹|樹的形狀和大小表示的是排序算法的功能和需要排序的元素個數(shù)|樹的高度表示了算法的運行時間|任何排序決策樹都有n!個葉子|第9章 排序

30、|以比較為基礎(chǔ)的排序算法的下界|根據(jù)數(shù)據(jù)結(jié)構(gòu)中關(guān)于二叉樹的性質(zhì)，有：|最壞情況：任何排序算法至少要做|次比較|平均情況：任何排序算法的平均比較次數(shù)的下界是|結(jié)論：具有O(nlgn)復(fù)雜度的比較排序算法在漸進意義下是最優(yōu)的算法|nnnn443. 1lg!lgnnnn443. 1lg!lg第9章 排序是一種借助多關(guān)鍵字排序的思想對單邏輯關(guān)鍵字進行排序的方法。是一種借助多關(guān)鍵字排序的思想對單邏輯關(guān)鍵字進行排序的方法。1. 多關(guān)鍵字排序多關(guān)鍵字排序撲克牌問題撲克牌問題 :已知撲克牌中已知撲克牌中52張牌面的次序關(guān)系定義為張牌面的次序關(guān)系定義為: 花樣花樣:面值面值:2 3 A. . .例，例， 8 3

31、花色優(yōu)先級更高，花色優(yōu)先級更高，為主關(guān)鍵字，面為主關(guān)鍵字，面值為次關(guān)鍵字值為次關(guān)鍵字第9章 排序2. 52張牌排序方法張牌排序方法 :最高位優(yōu)先法最高位優(yōu)先法(MSDF) :先按不同先按不同“花樣分成有次序的花樣分成有次序的4堆，每一堆均具有相同的花色；堆，每一堆均具有相同的花色；然后分別對每一堆按然后分別對每一堆按“面值大小整理有序。面值大小整理有序。最低位優(yōu)先法最低位優(yōu)先法(LSDF) :先按不同先按不同“面值分成面值分成 13 堆堆 ；然后將這然后將這 13 堆牌自小至大疊在一起堆牌自小至大疊在一起( 2 , 3 , . . . , A ) ；然后將這付牌整個顛倒過來再重新按不同的然后將

32、這付牌整個顛倒過來再重新按不同的“花樣分成花樣分成 4 堆堆 ；最后將這最后將這 4 堆牌按自小至大的次序合在一起堆牌按自小至大的次序合在一起 。搜集搜集分配分配第9章 排序3. 基數(shù)排序基數(shù)排序基數(shù)排序就是借助于基數(shù)排序就是借助于“分配和分配和“搜集兩種操作實現(xiàn)對單邏輯關(guān)搜集兩種操作實現(xiàn)對單邏輯關(guān)鍵字的排序。鍵字的排序。首先，單邏輯關(guān)鍵字通常都可以看作是由若干關(guān)鍵字復(fù)合而成。首先，單邏輯關(guān)鍵字通常都可以看作是由若干關(guān)鍵字復(fù)合而成。其次，利用其次，利用 LSDF 法實現(xiàn)對若干關(guān)鍵字的排序。法實現(xiàn)對若干關(guān)鍵字的排序。例，若關(guān)鍵字是數(shù)值，且值域為例，若關(guān)鍵字是數(shù)值，且值域為 0K999 ，故可以將

33、故可以將 K 看作是由看作是由 3 個關(guān)鍵字個關(guān)鍵字 K0 K1 K2 組成，組成，例，例，603是由是由 6 0 3 組成。組成。第9章 排序例，序列例，序列 278 109 063 930 589 184 505 269 008 083第一趟分配第一趟分配0 1 2 3 4 5 6 7 8 9278 109063930589184505269008083第一趟收集第一趟收集930063 083184505278 008109 589 269第二趟分配第二趟分配0 1 2 3 4 5 6 7 8 9930063083184505278008109589269第二趟收集第二趟收集505 008

34、 109930063 269278083 184 589第9章 排序第二趟收集第二趟收集505 008 109930063 269278083 184 589第三趟分配第三趟分配0 1 2 3 4 5 6 7 8 9505008 109930063269278083184589第三趟收集第三趟收集008 063 083109 184269 278505 589930第9章 排序中序遍歷可實現(xiàn)二叉搜索樹結(jié)點的有序化中序遍歷可實現(xiàn)二叉搜索樹結(jié)點的有序化 13 8523 1837 95 8 9 13 18 23 37? 如何實現(xiàn)如何實現(xiàn)自大到小排自大到小排列列第9章 排序各種內(nèi)排序方法的選擇各種內(nèi)排序方法的選擇1從時間復(fù)雜度選擇從時間復(fù)雜度選擇對元素個數(shù)較多的排序，可以選快速排序、堆排序、歸對元素個數(shù)較多的排序，可以選快速排序、堆排序、歸并排序，元素個數(shù)較少時，可以選簡單的排序方法。并排