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

1、第9章 排序設(shè)設(shè) n 個(gè)記錄的序列為個(gè)記錄的序列為 R1 , R2 , R3 , . . . , Rn 其相應(yīng)的關(guān)鍵字序列為其相應(yīng)的關(guān)鍵字序列為 K1 , K2 , K3 , . . . , Kn 若規(guī)定若規(guī)定 1 , 2 , 3 , . . . , n 的一個(gè)排列的一個(gè)排列 p1 , p2 , p3 , . . . , pn ，使得相應(yīng)的關(guān)鍵字滿足如下非遞減關(guān)系使得相應(yīng)的關(guān)鍵字滿足如下非遞減關(guān)系:Kp Kp Kp . . . Kp123n則原序列變?yōu)橐粋€(gè)按關(guān)鍵字有序的序列則原序列變?yōu)橐粋€(gè)按關(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)定的穩(wěn)定排序與不穩(wěn)定排序第9章 排序內(nèi)部排序內(nèi)部排序: 指的是待排序記錄存放在計(jì)算機(jī)指的是待排

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

4、間復(fù)雜性，而且要分析它的空間復(fù)雜性、穩(wěn)定性和簡單性等。第9章 排序按照排序過程中所依據(jù)的原則的不同可以分類為按照排序過程中所依據(jù)的原則的不同可以分類為: 插入排序插入排序 交換排序交換排序(快速排序快速排序) 選擇排序選擇排序 歸并排序歸并排序 基數(shù)排序基數(shù)排序 二叉排序樹排序二叉排序樹排序內(nèi)部排序第9章 排序思想思想: 利用有序表的插入操作進(jìn)行排序利用有序表的插入操作進(jìn)行排序有序表的插入有序表的插入: 將一個(gè)記錄插入到已排好序的有序表中，將一個(gè)記錄插入到已排好序的有序表中，從而得到一個(gè)新的有序表。從而得到一個(gè)新的有序表。例，序列例，序列 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 個(gè)元素作為初始有序表；個(gè)元素作為初始有序表；依次插入第依次插入第 2 , 3 , , k 個(gè)元素構(gòu)造新的有序表；個(gè)元素構(gòu)造新的有序表；直至最后一個(gè)元素；直至最后一個(gè)元素； 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)用比較比較和和移動(dòng)移動(dòng)兩種操作。兩種

6、操作。直接插入排序算法描述第9章 排序void insertsort(ElemType R,int n)/待排序元素用一個(gè)數(shù)組R表示，數(shù)組有n個(gè)元素 for ( int i=1; i=0)& (tempRj) Rj+1=Rj; j-; / 順序比較和移動(dòng) Rj+1=temp;第9章 排序 直接插入排序的效率分析直接插入排序的效率分析從空間來看，它只需要一個(gè)元素的輔助空間，用于元素的位置交換。從時(shí)間分析，首先外層循環(huán)要進(jìn)行n-1次插入，每次插入最少比較一次（正序），移動(dòng)兩次；最多比較i次，移動(dòng)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因此，直接插入排序的時(shí)間復(fù)雜度為O（n2）。直接插入算法的元素移動(dòng)是順序的，該方法是穩(wěn)定的。第9章 排序由于直接插入排序算法利用了有序表的插入操作，由于直接插入排序算法利用了有序表的插入操作，故故順序查找順序查找操作可以替換為操作可以替換為折半查找折半查找操作。操作。例，序列例，序列 49 38 65 97 76 13 27 設(shè)已形成有序表設(shè)已形成有序表 38 49 65 97 76 插入元素插入元素 13折半插入排序第9章 排序算法:void Bin

8、aryInsertSort(ElemType R,int n) for(int i=1; in; i+) /共進(jìn)行n-1次插入 int left=0,right=i-1;ElemType temp=Ri; while(left=right) int middle=(left+right)/2; /取中點(diǎn) if(temp=left;j-) Rj+1=Rj; /元素后移空出插入位 Rleft=temp; 第9章 排序折半插入效率分析二分插入算法與直接插入算法相比，需要輔助空間與直接插入排序基本一致；時(shí)間上，前者的比較次數(shù)比直接插入查找的最壞情況好，最好的情況壞，兩種方法的元素的移動(dòng)次數(shù)相同，因此二

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

10、體進(jìn)行一次直接插入排序。例，序列例，序列 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章 排序希爾排序效率分析希爾排序的時(shí)間復(fù)雜性在O（nlog2n）和O（n2 ）之間，大致為O（n1.3）。第9章 排序思想思想: 通過不斷比

12、較相鄰元素大小，進(jìn)行交換來實(shí)現(xiàn)排序。通過不斷比較相鄰元素大小，進(jìn)行交換來實(shí)現(xiàn)排序。首先將第一個(gè)元素與第二個(gè)元素比較大小，若為逆序，則交換；首先將第一個(gè)元素與第二個(gè)元素比較大小，若為逆序，則交換；然后比較第二個(gè)元素與第三個(gè)元素的大小，若為逆序，則交換；然后比較第二個(gè)元素與第三個(gè)元素的大小，若為逆序，則交換；. . .直至比較第直至比較第 n- -1 個(gè)元素與第個(gè)元素與第 n 個(gè)元素的大小，若為逆序，則交換；個(gè)元素的大小，若為逆序，則交換；第一趟排序第一趟排序:結(jié)果結(jié)果:關(guān)鍵字最大關(guān)鍵字最大的記錄被交換至的記錄被交換至最后最后一個(gè)元素位置上。一個(gè)元素位置上。交換排序冒泡排序第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章 排序冒泡排序的算法實(shí)現(xiàn)冒泡排序的算法實(shí)現(xiàn)。void Bubblesort(ElemType R,int n) int flag=1; /當(dāng)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; /交換，并標(biāo)記發(fā)生了交換 if(flag=0)return; 第9章 排序冒泡排序的效率分析冒泡排序的效率分析從冒泡排序的算法可以看出，若待排序的元素為正序，則只需進(jìn)行一趟排序，比較次數(shù)為（n-1）次，移動(dòng)元素次數(shù)為0；若待排序的元素為逆序，則需進(jìn)行n-1趟排序，比較次數(shù)為(n2-n)/2，移動(dòng)次數(shù)為3(n2-n )/2，因此冒泡排序算法的時(shí)間復(fù)雜度為O（n2）。由于其中的元素移動(dòng)較多，所以屬于內(nèi)排序中速度較慢的一種。因?yàn)槊芭菖判蛩惴ㄖ贿M(jìn)行元素間的順序移動(dòng)，所以是一個(gè)穩(wěn)定的算法。第9章 排序冒泡排序的一種改進(jìn)算法。冒泡排序的一種改進(jìn)算法。思想思想:以以首記

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

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

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

18、yhigh = Arraylow; / /在作為快排序的子程序時(shí)不用 Arraylow = pivot; return low;第9章 排序快排序（Quick Sort)|快排序-算法z快排序算法是個(gè)遞歸地對(duì)序列進(jìn)行分割的過程，遞歸終止的條件是最終序列長度為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ū)間的長度大致相 等 ） ， 則 結(jié) 點(diǎn) 數(shù) n 與 二 叉 樹 深 度 h 應(yīng) 滿 足log2nhlog2n+1 ，所以總的比較次數(shù)不會(huì)超過(n+1) log2n。因此，快速排序的最好時(shí)間復(fù)雜度應(yīng)為O（nlog2n）。而且在理論上已經(jīng)證明，快速排序的平均時(shí)間復(fù)雜度也為O（nlog2n）。若快速排序出現(xiàn)最壞的情形（每次能劃分成兩個(gè)子區(qū)間，但其中一個(gè)是空），則這時(shí)得到的二叉樹是一棵單分枝樹，得到的非

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

21、的記錄，并和第個(gè)記錄中選擇關(guān)鍵字最小的記錄，并和第 1 個(gè)個(gè)記錄交換。記錄交換。第第 2 趟選擇趟選擇: 從從 2n 個(gè)記錄中選擇關(guān)鍵字最小的記錄，并和第個(gè)記錄中選擇關(guān)鍵字最小的記錄，并和第 2 個(gè)個(gè)記錄交換。記錄交換。第第n- -1趟選擇趟選擇: 從從 n- -1n 個(gè)記錄中選擇關(guān)鍵字最小的記錄，并和第個(gè)記錄中選擇關(guān)鍵字最小的記錄，并和第 n- -1 個(gè)記錄交換。個(gè)記錄交換。. . .簡單選擇排序第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; /選擇具有最小排序碼的對(duì)象 for ( int j = i+1; j CurrentSize; j+) if ( Vectorj Vectork ) k = j; /當(dāng)前具最小排序碼的對(duì)象 if ( k != i ) /對(duì)換到第 i 個(gè)位置 Swap ( Vectori, Vectork

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

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

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

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

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

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

29、元素中繼續(xù)挑最小的元素進(jìn)行比較，確定C的第二個(gè)元素，依次類推，就可以完成對(duì)A和B的歸并， 其復(fù)雜度為O(n)第9章 排序歸并排序（Merge Sort)|歸并-合并兩個(gè)有序的序列第9章 排序歸并排序（Merge Sort)|歸并-合并兩個(gè)有序的序列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)|歸并-合并一個(gè)序列中的兩個(gè)有序的數(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é)點(diǎn)，則每個(gè)以比較為基礎(chǔ)的排序算法都可以用一個(gè)二叉樹來表示，其中一個(gè)中間節(jié)點(diǎn)表示一次比較，葉子節(jié)點(diǎn)表示排

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

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

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

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

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

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章 排序中序遍歷可實(shí)現(xiàn)二叉搜索樹結(jié)點(diǎn)的有序化中序遍歷可實(shí)現(xiàn)二叉搜索樹結(jié)點(diǎn)的有序化 13 8523 1837 95 8 9 13 18 23