數(shù)據(jù)結構之樹和圖算法課件

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

2、為排序排序。排序第9章 排序假設假設 Ki = Kj ，且排序前序列中，且排序前序列中 Ri 領先于領先于 Rj ；若在排序后的序列中若在排序后的序列中 Ri 仍領先于仍領先于 Rj ，則稱排序方法是，則稱排序方法是穩(wěn)定的穩(wěn)定的。若在排序后的序列中若在排序后的序列中 Rj 仍領先于仍領先于 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)定的穩(wěn)定排序與不穩(wěn)定排序第9章 排序內部排序內部排序: 指的是待排序記錄存放在計算機指的是待排

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

4、間復雜性，而且要分析它的空間復雜性、穩(wěn)定性和簡單性等。第9章 排序按照排序過程中所依據(jù)的原則的不同可以分類為按照排序過程中所依據(jù)的原則的不同可以分類為: 插入排序插入排序 交換排序交換排序(快速排序快速排序) 選擇排序選擇排序 歸并排序歸并排序 基數(shù)排序基數(shù)排序 二叉排序樹排序二叉排序樹排序內部排序第9章 排序思想思想: 利用有序表的插入操作進行排序利用有序表的插入操作進行排序有序表的插入有序表的插入: 將一個記錄插入到已排好序的有序表中，將一個記錄插入到已排好序的有序表中，從而得到一個新的有序表。從而得到一個新的有序表。例，序列例，序列 13 27 38 65 76 97 插入插入 4913

5、 27 38 49 65 76 97插入排序直接插入排序第9章 排序例，序列例，序列 49 38 65 97 76 13 27 初始，初始，S = 49 ； 38 49 初始，令第初始，令第 1 個元素作為初始有序表；個元素作為初始有序表；依次插入第依次插入第 2 , 3 , , k 個元素構造新的有序表；個元素構造新的有序表；直至最后一個元素；直至最后一個元素； 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 直接插入排序算法主要應用直接插入排序算法主要應用比較比較和和移動移動兩種操作。兩種

6、操作。直接插入排序算法描述第9章 排序void insertsort(ElemType R,int 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=2（n-1）Cmax=1+2

7、+n-1=（n2-n）/2 M max=3+4+n+1=（n2+3n-4）/2Cave=（n2+n-2）/4 M max=（n2+7n-8）/4因此，直接插入排序的時間復雜度為O（n2）。直接插入算法的元素移動是順序的，該方法是穩(wěn)定的。第9章 排序由于直接插入排序算法利用了有序表的插入操作，由于直接插入排序算法利用了有序表的插入操作，故故順序查找順序查找操作可以替換為操作可以替換為折半查找折半查找操作。操作。例，序列例，序列 49 38 65 97 76 13 27 設已形成有序表設已形成有序表 38 49 65 97 76 插入元素插入元素 13折半插入排序第9章 排序算法:void Bin

8、aryInsertSort(ElemType R,int n) for(int i=1; in; i+) /共進行n-1次插入 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ù)相同，因此二

9、分插入排序的時間復雜度仍為O(n2)。二分插入算法與直接插入算法的元素移動一樣是順序的，因此該方法也是穩(wěn)定的。第9章 排序分析直接插入排序分析直接插入排序1. 若待排序記錄序列按關鍵字若待排序記錄序列按關鍵字基本有序基本有序，則排序效，則排序效率可大大提高；率可大大提高；2. 待排序記錄總數(shù)越少，排序效率越高；待排序記錄總數(shù)越少，排序效率越高；希爾(shell)排序第9章 排序思想思想: 先將待排序記錄序列分割成為若干子序列分別進行直接插入排序；先將待排序記錄序列分割成為若干子序列分別進行直接插入排序；待整個序列中的記錄基本有序后，再全體進行一次直接插入排序。待整個序列中的記錄基本有序后，再全

10、體進行一次直接插入排序。例，序列例，序列 49 38 65 97 76 13 27 48 55 4 19 第一趟排序第一趟排序49 13 1938 2765 4897 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章 排序template void ShellSort (T Vector,

11、int arrSize ) T temp; int gap = arrSize / 2; /gap是子序列間隔 while ( gap != 0 ) /循環(huán),直到gap為零 for ( int i = gap; i = gap; j -= gap ) if ( temp Vectorj-gap ) Vectorj = Vectorj-gap; else break; Vectorj = temp; gap = ( int ) ( gap / 2 ); 第9章 排序希爾排序效率分析希爾排序的時間復雜性在O（nlog2n）和O（n2 ）之間，大致為O（n1.3）。第9章 排序思想思想: 通過不斷比

12、較相鄰元素大小，進行交換來實現(xiàn)排序。通過不斷比較相鄰元素大小，進行交換來實現(xiàn)排序。首先將第一個元素與第二個元素比較大小，若為逆序，則交換；首先將第一個元素與第二個元素比較大小，若為逆序，則交換；然后比較第二個元素與第三個元素的大小，若為逆序，則交換；然后比較第二個元素與第三個元素的大小，若為逆序，則交換；. . .直至比較第直至比較第 n- -1 個元素與第個元素與第 n 個元素的大小，若為逆序，則交換；個元素的大小，若為逆序，則交換；第一趟排序第一趟排序:結果結果:關鍵字最大關鍵字最大的記錄被交換至的記錄被交換至最后最后一個元素位置上。一個元素位置上。交換排序冒泡排序第9章 排序例，序列例，

13、序列 49 38 76 13 2749 38 76 13 2738 49 13 27 38 4913 7627 76初始初始第一趟排序后第一趟排序后最大值最大值13 4927 49次大值次大值第二趟排序后第二趟排序后38 13 2713 2713 38 27 38第三趟排序后第三趟排序后第四趟排序后第四趟排序后第9章 排序冒泡排序的算法實現(xiàn)冒泡排序的算法實現(xiàn)。void Bubblesort(ElemType R,int n) int flag=1; /當flag為0則停止排序 for (int i=1; i=i; j-) if (RjRj-1) /發(fā)生逆序 ElemType t=Rj;Rj=R

14、j-1;Rj-1=t;flag=1; /交換，并標記發(fā)生了交換 if(flag=0)return; 第9章 排序冒泡排序的效率分析冒泡排序的效率分析從冒泡排序的算法可以看出，若待排序的元素為正序，則只需進行一趟排序，比較次數(shù)為（n-1）次，移動元素次數(shù)為0；若待排序的元素為逆序，則需進行n-1趟排序，比較次數(shù)為(n2-n)/2，移動次數(shù)為3(n2-n )/2，因此冒泡排序算法的時間復雜度為O（n2）。由于其中的元素移動較多，所以屬于內排序中速度較慢的一種。因為冒泡排序算法只進行元素間的順序移動，所以是一個穩(wěn)定的算法。第9章 排序冒泡排序的一種改進算法。冒泡排序的一種改進算法。思想思想:以以首記

15、錄首記錄作為作為軸記錄軸記錄，從前、后雙向掃描序列，通過交換，實，從前、后雙向掃描序列，通過交換，實現(xiàn)大值記錄后移，小值記錄前移，最終將軸記錄安置在一個適現(xiàn)大值記錄后移，小值記錄前移，最終將軸記錄安置在一個適當?shù)奈恢?。當?shù)奈恢谩?小值記錄在前、大值記錄在后小值記錄在前、大值記錄在后)軸記錄軸記錄將原序列分割成兩部分，依次對前后兩部分重新設定軸將原序列分割成兩部分，依次對前后兩部分重新設定軸記錄，繼而分別再進行快速排序。記錄，繼而分別再進行快速排序。直至整個序列有序。直至整個序列有序。交換排序快速排序第9章 排序快排序（Quick Sort) 快速排序實例n快排序算法思想第9章 排序快排序（Qu

16、ick Sort)|快排序-分割過程z快排序是一個分治算法（也是第一個）z快排序的關鍵過程是每次遞歸的分割過程z分割問題描述：對一個序列，取它的一個元素作為軸，把所有小于軸的元素放在它的左邊，大于它的元素放在它的右邊z分割算法：用臨時變量對軸備份取兩個指針low和high，它們的初始值就是序列的兩端下標，在整個過程中保證low不大于high移動兩個指針l首先從high所指的位置向左搜索，找到第一個小于軸的元素, 把這個元素放在low的位置l再從low開始向右，找到第一個大于軸的元素，把它放在high的位置第9章 排序快排序（Quick Sort)|快排序-分割過程z分割算法：重復上述過程，直到

17、low=high，把軸放在low所指的位置這樣所有大于軸的元素被放在右邊，所有小于軸的元素被放在左邊第9章 排序快排序（Quick Sort)|快排序-分割過程第9章 排序快排序（Quick Sort)|快排序-分割過程int Partition(T Array, int low, int high) T pivot = Arraylow;/ while(low high) /在作為快排序的子程序時不用 while(low = pivot)high -; Arraylow = Arrayhigh; while(low high & Arraylow = pivot)low+; Arra

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

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

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

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

22、min38 49 65 97 76第第 4 趟選擇趟選擇:min38 49 65 76 97第9章 排序template void SelectSort ( T Vector, int CurrentSize) for ( int i = 0; i CurrentSize-1; i+ ) int k = i; /選擇具有最小排序碼的對象 for ( int j = i+1; j CurrentSize; j+) if ( Vectorj Vectork ) k = j; /當前具最小排序碼的對象 if ( k != i ) /對換到第 i 個位置 Swap ( Vectori, Vectork

23、 ); 第9章 排序選擇排序的主要操作是進行關鍵字間的選擇排序的主要操作是進行關鍵字間的比較比較。在在 n 個關鍵字中選出最小值，至少需要個關鍵字中選出最小值，至少需要 n- -1 次比較次比較。在剩余的在剩余的 n- -1 個關鍵字中選出最小值，至少需要個關鍵字中選出最小值，至少需要 n- -2 次比較次比較？如果能利用前如果能利用前 n- -1 次比較所得信息，可以減少后面選擇次比較所得信息，可以減少后面選擇的比較次數(shù)。的比較次數(shù)。體育比賽中的錦標賽體育比賽中的錦標賽:第9章 排序例，例，8 名運動員要決出名運動員要決出 冠、亞、季軍。冠、亞、季軍。按簡單選擇排序需要比賽按簡單選擇排序需要

24、比賽 7+6+5 = 18 場。場。若能夠利用以前的比賽結果，比賽場次實際可以減少為若能夠利用以前的比賽結果，比賽場次實際可以減少為 11 場。場。前提前提: 若若 甲甲 勝勝 乙乙 ，乙，乙 勝勝 丙丙 ，則，則 甲甲 必能勝必能勝 丙丙 。ZhaoChaLiuBaoDiaoYangXueWangBaoBaoDiaoChaBaoDiaoWang冠軍冠軍第9章 排序如何求如何求 亞軍？亞軍？ZhaoChaLiuDiaoYangXueWangChaDiaoCha亞軍亞軍可以利用前面的比賽結果！可以利用前面的比賽結果！ChaLiuDiaoWang第9章 排序如何求如何求 季軍？季軍？ZhaoLiu

25、DiaoYangXueWangLiuDiaoDiao季軍季軍同樣可以利用前面的比賽結果！同樣可以利用前面的比賽結果！LiuDiaoWangZhao第9章 排序又稱錦標賽排序，是一種按照錦標賽的思想進行選擇排序的方又稱錦標賽排序，是一種按照錦標賽的思想進行選擇排序的方法。法。例，序列例，序列 49 38 65 97 76 13 27 50第一趟選擇第一趟選擇133813493865977613275038651327最小值最小值樹形選擇排序第9章 排序第二趟選擇第二趟選擇2738274938659776275038657627次小值次小值第三趟選擇第三趟選擇3838504938659776503

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

27、；4. 刪除根結點，繼續(xù)改造剩余樹成堆，便可獲取刪除根結點，繼續(xù)改造剩余樹成堆，便可獲取次小值次小值 ；5. 輸出次小值輸出次小值 ；6. 重復改造，輸出次次小值、次次次小值，直至所有結點均重復改造，輸出次次小值、次次次小值，直至所有結點均輸出，便得到一個排序輸出，便得到一個排序 。1. 將序列構造成一棵完全二叉樹將序列構造成一棵完全二叉樹 ；第9章 排序例，序列例，序列 49 38 65 97 76 13 27 501. 按順序依次構造成完全二叉樹的結點；按順序依次構造成完全二叉樹的結點；49386597761327502. 把完全二叉樹改造成把完全二叉樹改造成堆堆；從下向上，父子交換；從下

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

29、元素中繼續(xù)挑最小的元素進行比較，確定C的第二個元素，依次類推，就可以完成對A和B的歸并， 其復雜度為O(n)第9章 排序歸并排序（Merge Sort)|歸并-合并兩個有序的序列第9章 排序歸并排序（Merge Sort)|歸并-合并兩個有序的序列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章

30、 排序歸并排序（Merge Sort)|歸并-合并一個序列中的兩個有序的數(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), z如果以每次比較作為節(jié)點，則每個以比較為基礎的排序算法都可以用一個二叉樹來表示，其中一個中間節(jié)點表示一次比較，葉子節(jié)點表示排

31、序的一種結果，這樣的二叉樹稱為判定樹或決策樹z舉例：比如有一個序列a, b, c(a,b,c互不相等） ，下列算法：先比較a和b, 再比較a和c，最后比較b和c 可以用下面的判定樹表示第9章 排序歸并排序（Merge Sort)|以比較為基礎的排序算法的下界第9章 排序歸并排序（Merge Sort)|以比較為基礎的排序算法的下界z假設輸入為a,b,c, acb, 則算法執(zhí)行經(jīng)過的路線為(ab)(ac)(bc)，需要3次比較z假設輸入為a,b,c, bac, 則算法執(zhí)行經(jīng)過的路線為(ab)(ac) 需要2次比較z任何以比較為基礎的排序算法都可以表示為一棵決策樹樹的形狀和大小表示的是排序算法的功

32、能和需要排序的元素個數(shù)樹的高度表示了算法的運行時間任何排序決策樹都有n!個葉子第9章 排序歸并排序（Merge Sort)|以比較為基礎的排序算法的下界z根據(jù)數(shù)據(jù)結構中關于二叉樹的性質，有：z最壞情況：任何排序算法至少要做次比較z平均情況：任何排序算法的平均比較次數(shù)的下界是z結論：具有O(nlgn)復雜度的比較排序算法在漸進意義下是最優(yōu)的算法nnnn443. 1lg!lgnnnn443. 1lg!lg第9章 排序是一種借助多關鍵字排序的思想對單邏輯關鍵字進行排序的方法。是一種借助多關鍵字排序的思想對單邏輯關鍵字進行排序的方法。1. 多關鍵字排序多關鍵字排序撲克牌問題撲克牌問題 :已知撲克牌中已

33、知撲克牌中52張牌面的次序關系定義為張牌面的次序關系定義為: 花色花色:面值面值:2 3 A. . .例，例， 8 3花色優(yōu)先級更高，花色優(yōu)先級更高，為主關鍵字，面為主關鍵字，面值為次關鍵字值為次關鍵字基數(shù)排序第9章 排序2. 52張牌排序方法張牌排序方法 :最高位優(yōu)先法最高位優(yōu)先法(MSDF) :先按不同先按不同“花色花色”分成有次序的分成有次序的4堆，每一堆均具有相同的花色；堆，每一堆均具有相同的花色；然后分別對每一堆按然后分別對每一堆按“面值面值”大小整理有序。大小整理有序。最低位優(yōu)先法最低位優(yōu)先法(LSDF) :先按不同先按不同“面值面值”分成分成 13 堆堆 ；然后將這然后將這 13

34、 堆牌自小至大疊在一起堆牌自小至大疊在一起( 2 , 3 , . . . , A ) ；然后將這付牌整個顛倒過來再重新按不同的然后將這付牌整個顛倒過來再重新按不同的“花色花色”分成分成 4 堆堆 ；最后將這最后將這 4 堆牌按自小至大的次序合在一起堆牌按自小至大的次序合在一起 。收集收集分配分配第9章 排序3. 基數(shù)排序基數(shù)排序基數(shù)排序就是借助于基數(shù)排序就是借助于“分配分配”和和“收集收集”兩種操作實現(xiàn)對單邏輯關兩種操作實現(xiàn)對單邏輯關鍵字的排序。鍵字的排序。首先，單邏輯關鍵字通常都可以看作是由若干關鍵字復合而成。首先，單邏輯關鍵字通常都可以看作是由若干關鍵字復合而成。其次，利用其次，利用 LS

35、DF 法實現(xiàn)對若干關鍵字的排序。法實現(xiàn)對若干關鍵字的排序。例，若關鍵字是數(shù)值，且值域為例，若關鍵字是數(shù)值，且值域為 0K999 ，故可以將故可以將 K 看作是由看作是由 3 個關鍵字個關鍵字 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第二趟分配第二

36、趟分配0 1 2 3 4 5 6 7 8 9930063083184505278008109589269第二趟收集第二趟收集505 008 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)二叉搜索樹結點的有序化中序遍歷可實現(xiàn)二叉搜索樹結點的有序化 13 8523 1837 95 8 9 13 18 23