華東理工815數(shù)據(jù)結(jié)構(gòu)chap7_排序_V2003

1、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 第七章第七章 內(nèi)部排序內(nèi)部排序 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 第七章第七章 內(nèi)部排序內(nèi)部排序 教學(xué)內(nèi)容教學(xué)內(nèi)容1、插入排序（直接插入排序、折半插入排序、插入排序（直接插入排序、折半插入排序、 希爾排序）；希爾排序）； 2、交換排序（起泡排序、快速排序）；、交換排序（起泡排序、快速排序）； 3、選擇排序（直接選擇排序、堆排序）；、選擇排序（直接選擇排序、堆排序）； 4、歸并排序；、歸并排序； 5、基數(shù)排序；、基數(shù)排序； 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 第七章第七章 內(nèi)部排序內(nèi)部排序 排序：排序：將數(shù)據(jù)元素的一個任意序列，重新排列成一個將數(shù)據(jù)元素的一個任意序列，重新排列成一個的序列。的序列。 7.1 概述

2、概述 例：將關(guān)鍵字序列：例：將關(guān)鍵字序列：52, 49, 80, 36, 14, 58, 61, 23 調(diào)整為：調(diào)整為：14, 23, 36, 49, 52, 58, 61 , 80 一般情況下，假設(shè)含一般情況下，假設(shè)含 n 個記錄的序列為個記錄的序列為 R1, R2, , Rn ， 其相應(yīng)的關(guān)鍵字序列為其相應(yīng)的關(guān)鍵字序列為 K1, K2, , Kn 這些關(guān)鍵字相互之間必須可以進(jìn)行比較，即在它們之間存在著這些關(guān)鍵字相互之間必須可以進(jìn)行比較，即在它們之間存在著這這 樣一個關(guān)系樣一個關(guān)系 ： Kp1Kp2Kpn數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 第七章第七章 內(nèi)部排序內(nèi)部排序 若若 Ki 為記錄為記錄 Ri 的的關(guān)

3、鍵字，則排序關(guān)鍵字，則排序。 若若 Ki 為記錄為記錄 Ri 的的關(guān)鍵字，則排序關(guān)鍵字，則排序可以可以（因為（因為 會有相同的關(guān)鍵字）。會有相同的關(guān)鍵字）。 設(shè)設(shè) Ki = Kj (1in, 1jn, ij )，且在排序前的序列中，且在排序前的序列中 Ri 領(lǐng)先于領(lǐng)先于 Rj（即（即 i j ）。若在排序后的序列中）。若在排序后的序列中 Ri 仍領(lǐng)先于仍領(lǐng)先于 Rj，則，則 稱所用的稱所用的；反之，則稱所用的；反之，則稱所用的。 例：例：設(shè)排序前的關(guān)鍵字序列為：設(shè)排序前的關(guān)鍵字序列為：52, 49, 80, 36, 14, 58, , 23 若排序后的關(guān)鍵字序列為：若排序后的關(guān)鍵字序列為：14

4、, 23, 36, , 49, 52, 58, 80， 則則。 若排序后的關(guān)鍵字序列為：若排序后的關(guān)鍵字序列為：14, 23, , 36, 49, 52, 58, 80， 則則。 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 第七章第七章 內(nèi)部排序內(nèi)部排序 內(nèi)部排序和外部排序內(nèi)部排序和外部排序 若若整個排序過程不需要訪問外存整個排序過程不需要訪問外存便能完成，則稱此類排序問便能完成，則稱此類排序問 題為題為內(nèi)部排序內(nèi)部排序； 反之，若參加排序的記錄數(shù)量很大，整個序列的排序過程反之，若參加排序的記錄數(shù)量很大，整個序列的排序過程不不可能在內(nèi)存中完成可能在內(nèi)存中完成，則稱此類排序問題為，則稱此類排序問題為外部排序外部排序。 內(nèi)

5、部排序的方法內(nèi)部排序的方法 內(nèi)部排序的過程是一個逐步擴(kuò)大記錄的有序序列的過程。內(nèi)部排序的過程是一個逐步擴(kuò)大記錄的有序序列的過程。 有序序列區(qū)有序序列區(qū)無無 序序 序序 列列 區(qū)區(qū)有序序列區(qū)有序序列區(qū)無無 序序 序序 列列 區(qū)區(qū)經(jīng)過一趟排序經(jīng)過一趟排序 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 第七章第七章 內(nèi)部排序內(nèi)部排序 排序方法分類：排序方法分類： 1)、插入排序：、插入排序：直接插入排序、折半插入排序、希爾排序直接插入排序、折半插入排序、希爾排序 2)、交換排序：、交換排序：冒泡排序、快速排序冒泡排序、快速排序 3)、選擇排序：、選擇排序：簡單選擇排序、堆排序簡單選擇排序、堆排序 4)、歸并排序：、歸并排序：2

6、-路歸并排序路歸并排序 5)、基數(shù)排序、基數(shù)排序 基于不同的基于不同的“擴(kuò)大擴(kuò)大” 有序序列長度的方法，內(nèi)部排序有序序列長度的方法，內(nèi)部排序 方法大致可分下列幾種類型：方法大致可分下列幾種類型： 將無序子序列中的一將無序子序列中的一 個或幾個記錄個或幾個記錄“”到有到有 序序列中，從而增加記錄序序列中，從而增加記錄 的有序子序列的長度。的有序子序列的長度。 通過通過“”無序序列中的記錄從而無序序列中的記錄從而 得到其中得到其中關(guān)鍵字最小關(guān)鍵字最小或或最大最大的記錄，并的記錄，并 將它將它加入到有序子序列加入到有序子序列中，以此方法增中，以此方法增 加記錄的有序子序列的長度。加記錄的有序子序列的

7、長度。 從記錄的無序子序列中從記錄的無序子序列中“” 關(guān)鍵字最小關(guān)鍵字最小或或最大最大的記錄，并將它的記錄，并將它 加入到有序子序列加入到有序子序列中，以此方法增中，以此方法增 加記錄的有序子序列的長度。加記錄的有序子序列的長度。 通過通過“”兩個兩個 或兩個以上的記錄有或兩個以上的記錄有 序子序列，逐步增加序子序列，逐步增加 記錄有序序列的長度。記錄有序序列的長度。 基數(shù)排序是一種基于多基數(shù)排序是一種基于多 關(guān)鍵字排序的思想，將單關(guān)關(guān)鍵字排序的思想，將單關(guān) 鍵字按基數(shù)分成鍵字按基數(shù)分成 “多關(guān)鍵字多關(guān)鍵字” 進(jìn)行排序的方法。進(jìn)行排序的方法。 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 第七章第七章 內(nèi)部排序內(nèi)部排序

8、7.2 插入排序插入排序 有序序列有序序列 R1. i -1 Ri無序序列無序序列 Ri . n一趟直接插入排序的基本思想：一趟直接插入排序的基本思想： 有序序列有序序列 R1. i無序序列無序序列 Ri +1 . n實現(xiàn)實現(xiàn)“一趟插入排序一趟插入排序”可分可分三步三步進(jìn)行：進(jìn)行： 3將將 Ri 插入（復(fù)制）到插入（復(fù)制）到 R j+1 的位置上。的位置上。 2將將 R j+1 . i -1 中的所有記錄均后移一個位置；中的所有記錄均后移一個位置； 1在在 R1 . i -1 中查找中查找 Ri 的插入位置的插入位置j， R1 . j.key Ri.key R j+1 . i -1.key；

9、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 第七章第七章 內(nèi)部排序內(nèi)部排序 7.2.1 直接插入排序直接插入排序 初始狀態(tài)初始狀態(tài)4938659776132749 R0 R1 R2 R3 R4 R5 R6 R7 R8 i =2 i =3 3849659776132749 i =4 3849659776132749 i =5 384965769713274976i =6 384965769713274913i =7 384965769713274927i =8 3849657697132749494938659776132749 3849387 趟趟 排序排序 1 趟趟 排序排序 2 趟趟 排序排序 void Inser

10、tSort ( SqList &L ) / 對順序表對順序表 L 作直接插入排序。作直接插入排序。 for ( i = 2; i = L.length; + i ) if (L.ri.key L.ri -1.key) / InsertSort 排序過程：排序過程：先將序列中第先將序列中第 1 個記錄看成是一個有序子序列，個記錄看成是一個有序子序列， 然后從第然后從第 2 個記錄開始，逐個進(jìn)行插入，直至整個序列有序。個記錄開始，逐個進(jìn)行插入，直至整個序列有序。 在在 R1. i-1中查找中查找 Ri 的插入位置的插入位置; 對于在查找過程中找到的那些關(guān)鍵字對于在查找過程中找到的那些關(guān)鍵字

11、 不小于不小于 Ri.key 的記錄，在查找的同的記錄，在查找的同 時實現(xiàn)記錄向后移動；時實現(xiàn)記錄向后移動； L.r0 = L.ri; / 復(fù)制為監(jiān)視哨復(fù)制為監(jiān)視哨 L.ri = L.ri -1; for ( j = i - 2; L.r0.key L.r j .key; - - j ) L.r j + 1 = L.r j ; / 記錄后移記錄后移 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 第七章第七章 內(nèi)部排序內(nèi)部排序 算法分析算法分析 設(shè)待排序記錄個數(shù)為設(shè)待排序記錄個數(shù)為 n n，則該算法的主程序執(zhí)行，則該算法的主程序執(zhí)行n-1n-1趟。趟。關(guān)鍵字比較次數(shù)和記錄移動次數(shù)與記錄關(guān)鍵字的初始排關(guān)鍵字比較次數(shù)和記錄移動

12、次數(shù)與記錄關(guān)鍵字的初始排列有關(guān)。列有關(guān)。 最好情況下最好情況下, , 排序前記錄已按關(guān)鍵字的值從小到大有序排序前記錄已按關(guān)鍵字的值從小到大有序，每趟只需與前面有序記錄序列的最后一個記錄比較，每趟只需與前面有序記錄序列的最后一個記錄比較 1 1 次，移動次，移動 0 0 次記錄，總的關(guān)鍵字比較次數(shù)為次記錄，總的關(guān)鍵字比較次數(shù)為 n-1, n-1, 記錄記錄移動次數(shù)為移動次數(shù)為 0 0。 最壞情況下，第最壞情況下，第 i i 趟時第趟時第 i i 個記錄必須與前面?zhèn)€記錄必須與前面 i i 個記個記錄都做關(guān)鍵字比較，并且每做錄都做關(guān)鍵字比較，并且每做 1 1 次比較就要做次比較就要做 1 1 次數(shù)次

13、數(shù)據(jù)移動。據(jù)移動。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 第七章第七章 內(nèi)部排序內(nèi)部排序 112 nni2)1()1(2nnini2)1)(4()1(2nniniT(n)=O(n) 算法評價算法評價 時間復(fù)雜度：時間復(fù)雜度： 比較次數(shù)：比較次數(shù)： 移動次數(shù)：移動次數(shù)：0 最好的情況：最好的情況：待排序記錄按關(guān)鍵字從小到大排列（正序）待排序記錄按關(guān)鍵字從小到大排列（正序） 比較次數(shù)：比較次數(shù)： 移動次數(shù)：移動次數(shù)： 最壞的情況：最壞的情況：待排序記錄按關(guān)鍵字從大到小排列（逆序）待排序記錄按關(guān)鍵字從大到小排列（逆序） 空間復(fù)雜度：空間復(fù)雜度：S(n)=O(1) 直接插入排序是穩(wěn)定排序直接插入排序是穩(wěn)定排序 5 4 3

14、2 1 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 第七章第七章 內(nèi)部排序內(nèi)部排序 7.2.2 其他插入排序其他插入排序 1、折半插入排序：、折半插入排序：用折半查找方法確定插入位置的排序。用折半查找方法確定插入位置的排序。 void BInsertSort ( SqList &L ) ( i = 2; i = L.length; + i ) L.r0 = L.ri; low = 1; high = i -1; while (low = high +1; -j ) L.rj +1 = L.rj; / 記錄后移記錄后移 L.rhigh+1 = L.r0; / 插入插入 / / BInsertSorti =1 (3

15、0) 13 70 85 39 42 6 20 i =7 6 (6 13 30 39 42 70 85 ) 20 i =8 20 (6 13 30 39 42 70 85 ) 20 lhmmi =8 20 (6 13 30 39 42 70 85 ) 20 lhi =8 20 (6 13 30 39 42 70 85 ) 20 lhi =8 20 (6 13 20 30 39 42 70 85 ) i =8 20 (6 13 30 39 42 70 85 ) 20 lhmT(n)=O(n) 時間復(fù)雜度：時間復(fù)雜度： 空間復(fù)雜度：空間復(fù)雜度：S(n)=O(1) 折半插入排序是穩(wěn)定排序折半插入排序是

16、穩(wěn)定排序 僅減少了比較次數(shù)，僅減少了比較次數(shù)， 移動次數(shù)不變。移動次數(shù)不變。 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 第七章第七章 內(nèi)部排序內(nèi)部排序 7.2.3 希爾排序（縮小增量排序）希爾排序（縮小增量排序） 基本思想：對待排序列先作基本思想：對待排序列先作“宏觀宏觀”調(diào)整，調(diào)整，再作再作“微觀微觀”調(diào)整。調(diào)整。 排序過程：先取一個正整數(shù)排序過程：先取一個正整數(shù) d d1 1 n n作為增量，作為增量，把所把所有相隔有相隔 d d1 1 的記錄放在一組內(nèi)，組內(nèi)進(jìn)行直接插入排的記錄放在一組內(nèi)，組內(nèi)進(jìn)行直接插入排序；然后取序；然后取 增量增量d d2 2 d d1 1，重復(fù)上述分組和排序操作；重復(fù)上述分組和排序操作；

17、直至直至 d di i = 1 = 1，即所有記錄放進(jìn)一個組中排序為止。即所有記錄放進(jìn)一個組中排序為止。 其中其中 稱為稱為。 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 第七章第七章 內(nèi)部排序內(nèi)部排序 gap=40 1 2 3 4 5 6 7254925*08375216214925*375216212525*08371621254908520 1 2 3 4 5 6 7數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 第七章第七章 內(nèi)部排序內(nèi)部排序 結(jié)果結(jié)果gap=20 1 2 3 4 5 6 70825*253749162152數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 第七章第七章 內(nèi)部排序內(nèi)部排序 gap=10 1 2 3 4 5 6 7數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 第七章第七

18、章 內(nèi)部排序內(nèi)部排序 n開始時開始時 gap 的值較大的值較大, 子序列中的對象較少子序列中的對象較少, 排序速排序速度較快度較快; 隨著排序進(jìn)展隨著排序進(jìn)展, gap 值逐漸變小值逐漸變小, 子序列中子序列中對象個數(shù)逐漸變多對象個數(shù)逐漸變多, 由于前面大多數(shù)對象已基本有由于前面大多數(shù)對象已基本有序序, 所以排序速度仍然很快。所以排序速度仍然很快。nGap的取法有多種。的取法有多種。 shell 提出取提出取 gap = n/2 ，gap = gap/2 ，直到，直到gap = 1。n希爾排序所需的比較次數(shù)和移動次數(shù)約為希爾排序所需的比較次數(shù)和移動次數(shù)約為n 1.3當(dāng)當(dāng)n趨于無窮時可減少到趨于

19、無窮時可減少到n(log2 n)2數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 第七章第七章 內(nèi)部排序內(nèi)部排序 3、重復(fù)直到重復(fù)直到 “” 或或“” 為止。為止。 7.3 交換排序交換排序 1、冒泡排序、冒泡排序 v 排序過程排序過程 1、比較第一個記錄與第二個、比較第一個記錄與第二個 記錄，若記錄，若關(guān)鍵字關(guān)鍵字為逆序為逆序則交換；然則交換；然 后比較第二個記錄與第三個記錄；后比較第二個記錄與第三個記錄； 依次類推，直至第依次類推，直至第 n -1 個記錄和第個記錄和第 n 個記錄比較為止個記錄比較為止，結(jié)果關(guān)鍵字最大的記錄被安，結(jié)果關(guān)鍵字最大的記錄被安 置在最后一個記錄上。置在最后一個記錄上。 2、對前對前 n-1

20、個記錄進(jìn)行第二個記錄進(jìn)行第二 趟冒泡排序，結(jié)果使關(guān)鍵字次大的趟冒泡排序，結(jié)果使關(guān)鍵字次大的 記錄被安置在第記錄被安置在第 n-1 個記錄位置。個記錄位置。 初初 始始 關(guān)關(guān) 鍵鍵 字字 49 38 65 97 76 13 27 49 第第 一一 趟趟 排排 序序 49 38 49 97 76 97 97 13 97 97 27 97 97 49 38 49 65 76 13 27 49 38 49 65 13 27 49 第第 二二 趟趟 排排 序序 38 49 13 27 49 第第 三三 趟趟 排排 序序 38 13 27 49 第第 四四 趟趟 排排 序序 13 27 38第第 五五 趟

21、趟 排排 序序 第第 六六 趟趟 排排 序序 for ( j = 1; j ; j + +) if ( r j +1 r j ) r j r j + 1 ; for ( j = 1; j ; j + +) if ( r j +1 1; i - - ) ; while ( i 1) / while i = n ; /i控制排序的趟數(shù)控制排序的趟數(shù) i = k ; Void BubbleSort(SqList &L) 初初 始始 關(guān)關(guān) 鍵鍵 字字 49 38 65 97 76 13 27 49 k = j ; /交換的位置交換的位置 k = 1 ; 通過設(shè)置變量通過設(shè)置變量k記錄每趟排記錄

22、每趟排序最后的數(shù)據(jù)交換位置。序最后的數(shù)據(jù)交換位置。可以減少可以減少 總排序的趟數(shù)?？偱判虻奶藬?shù)。例：例： 5 2 3 1 9 7 8 2 3 1 5 7 8 9 2 1 3 5 7 8 9i = 6 i = 2 1 2 3 5 7 8 9i = 1 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 第七章第七章 內(nèi)部排序內(nèi)部排序 v 算法評價算法評價 時間復(fù)雜度：時間復(fù)雜度： 最好情況（正序）最好情況（正序） 比較次數(shù)：比較次數(shù)：n -1 移動次數(shù)：移動次數(shù)：0 T(n) = O(n) 最壞情況（逆序）最壞情況（逆序） 比較次數(shù)：比較次數(shù)： 移動次數(shù)：移動次數(shù)： )(21)1(22nnini )(23)1(322nnini

23、空間復(fù)雜度：空間復(fù)雜度：S(n) = O(1) 穩(wěn)定性：穩(wěn)定排序穩(wěn)定性：穩(wěn)定排序 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 第七章第七章 內(nèi)部排序內(nèi)部排序 基本思想：基本思想：一個記錄，以它的關(guān)鍵字作為一個記錄，以它的關(guān)鍵字作為“”，凡，凡關(guān)關(guān) 鍵字小于樞軸的記錄均移至樞軸之前，凡關(guān)鍵字大于樞軸的記鍵字小于樞軸的記錄均移至樞軸之前，凡關(guān)鍵字大于樞軸的記錄均移至樞軸之后。錄均移至樞軸之后。 2、一趟快速排序（一次劃分）、一趟快速排序（一次劃分） lowhigh設(shè)設(shè) Rs=52 為樞軸。為樞軸。 例：例： 52 49 80 36 14 58 61 97 23 75 st 附設(shè)兩個指針附設(shè)兩個指針 low 和和 high，

24、從，從 high 所指位置起向前搜索找所指位置起向前搜索找 到第一個關(guān)鍵字小于樞軸的關(guān)鍵字的記錄與樞軸記錄交換，然后到第一個關(guān)鍵字小于樞軸的關(guān)鍵字的記錄與樞軸記錄交換，然后 從從 low 所指位置起向后搜索找到第一個關(guān)鍵字大于樞軸的關(guān)鍵字所指位置起向后搜索找到第一個關(guān)鍵字大于樞軸的關(guān)鍵字 的記錄與樞軸記錄交換，重復(fù)這兩步直至的記錄與樞軸記錄交換，重復(fù)這兩步直至 low = high 為止。為止。 high23 low low80highhighhighhigh14lowlow數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 第七章第七章 內(nèi)部排序內(nèi)部排序 快速排序過程快速排序過程 3、快速排序、快速排序 首先對無序的記錄序列

25、進(jìn)行首先對無序的記錄序列進(jìn)行“一次劃分一次劃分”，之后分別對分割，之后分別對分割 所得兩個子序列所得兩個子序列“遞歸遞歸”進(jìn)行一趟快速排序。進(jìn)行一趟快速排序。無無 序序 的的 記記 錄錄 序序 列列無序記錄子序列無序記錄子序列 (1)無序子序列無序子序列 (2) 樞軸樞軸 一次劃分一次劃分 分別進(jìn)行一趟快速排序分別進(jìn)行一趟快速排序 有有 序序 的的 記記 錄錄 序序 列列 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 第七章第七章 內(nèi)部排序內(nèi)部排序 int Partition (SqList &L, int low, int high) pivotkey = L.rlow.key; /用子表的第一個記錄作樞軸記錄

26、用子表的第一個記錄作樞軸記錄 while (low high) while (low = pivotkey) - - high; / 將比樞軸小的記錄交換到低端將比樞軸小的記錄交換到低端 while (low high & L.rlow.key = pivotkey) + + low; / 將比樞軸大的記錄交換到高端將比樞軸大的記錄交換到高端 /while return low; / 返回樞軸所在位置返回樞軸所在位置 / PartitionL.r0=L.rlow;L.rlow=L.r0; 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 第七章第七章 內(nèi)部排序內(nèi)部排序 void QSort (SqList &

27、L, int low, int high ) / 對順序表對順序表 L 中的子序列中的子序列 L.rlow.high 進(jìn)行快速排序進(jìn)行快速排序 if (low high) / 長度大于長度大于1 / QSortQSort(L, low, pivotloc-1) ; / 對低子序列遞歸排序，對低子序列遞歸排序，pivotloc 是樞軸位置是樞軸位置 QSort(L, pivotloc+1, high); / 對高子序列遞歸排序?qū)Ω咦有蛄羞f歸排序 第一次調(diào)用函數(shù)第一次調(diào)用函數(shù) Qsort 時，待排序記錄序列的上、時，待排序記錄序列的上、 下界分別為下界分別為 1 和和 L.length。 void

28、 QuickSort( SqList & L) / 對順序表進(jìn)行快速排序?qū)樞虮磉M(jìn)行快速排序 QSort(L, 1, L.length); / QuickSort 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 第七章第七章 內(nèi)部排序內(nèi)部排序 n算法算法quicksort是一個遞歸的算法是一個遞歸的算法, 其遞歸樹其遞歸樹如圖所示。如圖所示。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 第七章第七章 內(nèi)部排序內(nèi)部排序 算法分析算法分析n快速排序的趟數(shù)取決于遞歸樹的高度?？焖倥判虻奶藬?shù)取決于遞歸樹的高度。n如果每次劃分對一個對象定位后如果每次劃分對一個對象定位后, 該對象的該對象的左側(cè)子序列與右側(cè)子序列的長度相同左側(cè)子序列與右側(cè)子序列的長度相同

29、, 則下則下 一步將是對兩個長度減半的子序列進(jìn)行排一步將是對兩個長度減半的子序列進(jìn)行排序序, 這是最理想的情況。這是最理想的情況。n在在 n個元素的序列中個元素的序列中, 對一個對象定位所需對一個對象定位所需時間為時間為 O(n)。若設(shè)。若設(shè) t (n) 是對是對 n 個元素的序個元素的序列進(jìn)行排序所需的時間列進(jìn)行排序所需的時間, 而且每次對一個對而且每次對一個對象正確定位后象正確定位后, 正好把序列劃分為長度相等正好把序列劃分為長度相等的兩個子序列的兩個子序列, 此時此時, 總的計算時間為：總的計算時間為：數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 第七章第七章 內(nèi)部排序內(nèi)部排序 T(n) cn + 2T(n/2 )

30、 / c 是一個常數(shù)是一個常數(shù) cn + 2 ( cn/2 + 2T(n/4) ) = 2cn + 4T(n/4) 2cn + 4 ( cn/4 +2T(n/8) ) = 3cn + 8T(n/8) cn log2n + nT(1) = O(n log2n )數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 第七章第七章 內(nèi)部排序內(nèi)部排序 n可以證明可以證明, 函數(shù)函數(shù)quicksort的平均時間復(fù)雜度的平均時間復(fù)雜度是是O(nlog2n)。實驗結(jié)果表明。實驗結(jié)果表明: 就平均計算時就平均計算時間而言間而言, 快速排序是所有內(nèi)排序方法中最好快速排序是所有內(nèi)排序方法中最好的一個。的一個。n快速排序是遞歸的，需要有一個棧存放每快

31、速排序是遞歸的，需要有一個棧存放每層遞歸調(diào)用時的指針和參數(shù)。層遞歸調(diào)用時的指針和參數(shù)。算法分析算法分析數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 第七章第七章 內(nèi)部排序內(nèi)部排序 n最大遞歸調(diào)用層次數(shù)與遞歸樹的高度一致最大遞歸調(diào)用層次數(shù)與遞歸樹的高度一致,理想情況為理想情況為 log2(n+1) 。因此，要求存儲。因此，要求存儲開銷為開銷為 O(log2n)。n在最壞的情況在最壞的情況, 即待排序?qū)ο笮蛄幸呀?jīng)按其即待排序?qū)ο笮蛄幸呀?jīng)按其排序碼從小到大排好序的情況下排序碼從小到大排好序的情況下, 其遞歸樹其遞歸樹成為單支樹成為單支樹, 每次劃分只得到一個比上一次每次劃分只得到一個比上一次少一個對象的子序列?？偟呐判虼a比較次

32、少一個對象的子序列。總的排序碼比較次數(shù)將達(dá)數(shù)將達(dá)n快速排序是一種不穩(wěn)定的排序方法。快速排序是一種不穩(wěn)定的排序方法。2121211nnninni)()(數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 第七章第七章 內(nèi)部排序內(nèi)部排序 7.4 選擇排序選擇排序 7.4.1 簡單選擇排序簡單選擇排序 排序過程：排序過程： 首先通過首先通過 n 1 次關(guān)鍵字比較，從次關(guān)鍵字比較，從 n 個記錄中找出個記錄中找出關(guān)鍵字最小關(guān)鍵字最小 的記錄，將它與第一個記錄交換。的記錄，將它與第一個記錄交換。 再通過再通過 n 2 次比較，從剩余的次比較，從剩余的 n 1 個記錄中找出關(guān)鍵字次小個記錄中找出關(guān)鍵字次小 的記錄，將它與第二個記錄交換。的

33、記錄，將它與第二個記錄交換。 重復(fù)上述操作，共進(jìn)行重復(fù)上述操作，共進(jìn)行 n 1 趟排序后，排序結(jié)束。趟排序后，排序結(jié)束。 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 第七章第七章 內(nèi)部排序內(nèi)部排序 假設(shè)排序過程中，待排記錄序列的狀態(tài)為：假設(shè)排序過程中，待排記錄序列的狀態(tài)為：有序序列有序序列 R1.i-1 無序序列無序序列 Ri.n 第第 i 趟趟簡單選擇排序簡單選擇排序從中選出從中選出關(guān)鍵字最小的記錄關(guān)鍵字最小的記錄有序序列有序序列R1.i無序序列無序序列 Ri+1.n數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 第七章第七章 內(nèi)部排序內(nèi)部排序 j+ if (L.rj.key L.rk.key) k = j; j = i+1; for (i =

34、1; i L.length; + i) 例：例： 初始：初始： 49 38 65 97 76 13 27 jjjjjjki =1 13 49 一趟：一趟： 13 38 65 97 76 49 27 i =2 二趟：二趟： 13 27 65 97 76 49 38 三趟：三趟： 13 27 38 97 76 49 65 四趟：四趟： 13 27 38 49 76 97 65 五趟：五趟： 13 27 38 49 65 97 76 六趟：六趟： 13 27 38 49 65 76 97 排序結(jié)束：六趟：排序結(jié)束：六趟： 13 27 38 49 65 76 97 kk = i; kfor ( j =

35、 i+1; j = n; j+) if (L.rj.key =0; i - - ) HeapAdjust (H.data, i, H.len-1); for ( i = H.len-1; i = 0; i - - ) Swap (H.data0, H.datai); / 將堆頂記錄和當(dāng)前未經(jīng)排序子序列將堆頂記錄和當(dāng)前未經(jīng)排序子序列 H.datai相互交換相互交換 HeapAdjust (H.r, 0, i -1); / 重建大根堆，自頂向下進(jìn)行篩選重建大根堆，自頂向下進(jìn)行篩選 定義堆類型為：定義堆類型為： typedef SqList HeapType; / 堆用順序表表示堆用順序表表示 數(shù)據(jù)

36、結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 第七章第七章 內(nèi)部排序內(nèi)部排序 除除 H.datas 之外均之外均滿足堆滿足堆的特征的特征void HeapAdjust (HeadType &H, int s, int m) / HeapAdjust int i=s, j=2*i+1;rc = H.datai; / 暫存暫存 H.dataswhile ( j= H.dataj.key ) break; / 再作再作“根根”和和“子樹根子樹根”之間的比較，若之間的比較，若“=”成立，則說明成立，則說明 / 已找到已找到 rc 的插入位置的插入位置 i ，不需要繼續(xù)往下調(diào)整，不需要繼續(xù)往下調(diào)整 else H.datai =

37、 H.dataj; i = j; j=2*j+1; / 否則記錄上移，尚需繼續(xù)往下調(diào)整否則記錄上移，尚需繼續(xù)往下調(diào)整 if ( j m & H.dataj.key H.dataj+1.key ) +j; / 左左/右右“子樹根子樹根”之間先之間先 進(jìn)行相互比較，令進(jìn)行相互比較，令 j 指示關(guān)鍵字較大記錄的位置指示關(guān)鍵字較大記錄的位置 194825211608012345 19 48 21 25 16 08數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 第七章第七章 內(nèi)部排序內(nèi)部排序 堆排序的時間復(fù)雜度和空間復(fù)雜度：堆排序的時間復(fù)雜度和空間復(fù)雜度： 堆排序的時間復(fù)雜度為堆排序的時間復(fù)雜度為 O(nlogn)，與簡單選

38、擇排序，與簡單選擇排序 O(n2) 相比時間效率提高了很多。相比時間效率提高了很多。 空間復(fù)雜度：空間復(fù)雜度：S(n) = O(1) 堆排序是一種堆排序是一種且且的排序方法。的排序方法。 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 第七章第七章 內(nèi)部排序內(nèi)部排序 7.6 歸并排序歸并排序 歸并：歸并：將兩個或兩個以上的將兩個或兩個以上的有序有序表合并成一個新的有序表。表合并成一個新的有序表。 例如：原始序列例如：原始序列L 中有兩個有序子表中有兩個有序子表 Lleft Lmid和和Lmid+1 Lright。08 21 25 25* 49 62 72 93 16 37 54 left mid mid+1 rightL0

39、8 16 21 25 25* 37 49 54 62 72 93 l eft rightL1k歸并成一個有序表，存于歸并成一個有序表，存于L1L1的的L1L1leftleft L1L1rightright 中。中。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 第七章第七章 內(nèi)部排序內(nèi)部排序 歸并歸并 為了實現(xiàn)兩路歸并，需要設(shè)置為了實現(xiàn)兩路歸并，需要設(shè)置 3 3 個指針：變量個指針：變量 i i 和和 j j 是表是表Lleft LmidLleft Lmid和和Lmid+1 LrightLmid+1 Lright的當(dāng)前的當(dāng)前檢測指針。檢測指針。k k 是表是表 L1 L1 的存放指針。的存放指針。 當(dāng)當(dāng) i i 和和 j

40、j 都在兩個表的表長內(nèi)變化時，根據(jù)對應(yīng)項都在兩個表的表長內(nèi)變化時，根據(jù)對應(yīng)項的關(guān)鍵字的大小，依次把關(guān)鍵字小的記錄排放到的關(guān)鍵字的大小，依次把關(guān)鍵字小的記錄排放到新表新表 k k 所指位置所指位置中；中；當(dāng)當(dāng) i i 與與 j j 中有一個已經(jīng)超出表長時，將另一個表中有一個已經(jīng)超出表長時，將另一個表中的剩余部分照抄到新表中。中的剩余部分照抄到新表中。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 第七章第七章 內(nèi)部排序內(nèi)部排序 left rightkL08 21 25 25* 49 62 72 93 16 37 54 left mid mid+1 rightL1ij08212525* 49627293543716iiiiii

41、ijjkkkkkkkkkk數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 第七章第七章 內(nèi)部排序內(nèi)部排序 void merge(dataList& L, dataList& L1, int left, int mid, int right) int i = left, j = mid+1, k = left; while (i = mid & j = right) /兩兩比較 while (i = mid) while (j = right) if (L.Vi.key = L.Vj.key) L1.Vk = L.Vi; i+; k+; else L1.Vk = L.Vj; j+; k+; L1.Vk

42、 = L.Vi; i+; k+; L1.Vk = L.Vj; j+; k+;數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 第七章第七章 內(nèi)部排序內(nèi)部排序 2-路歸并排序的算法思想路歸并排序的算法思想 初始關(guān)鍵字：初始關(guān)鍵字： 49 38 65 97 76 13 27 一趟歸并后：一趟歸并后： 38 49 65 97 13 76 27 二趟歸并后：二趟歸并后： 38 49 65 97 13 27 76 三趟歸并后：三趟歸并后： 13 27 38 49 65 76 97 看成是看成是 n 個有序的子個有序的子 序列（長度為序列（長度為 1），）， 然后兩兩歸并。然后兩兩歸并。 得到得到 n/2 個長度為個長度為 2 或或 1

43、 的有序子序列。的有序子序列。 空間復(fù)雜度為：空間復(fù)雜度為：O(n)。 時間復(fù)雜度為：時間復(fù)雜度為：O(nlog2n)。 穩(wěn)定。穩(wěn)定。 每趟歸并的時間復(fù)每趟歸并的時間復(fù)雜度為雜度為O(n)，共需進(jìn)，共需進(jìn)行行 log2n 趟。趟。在內(nèi)部排序中，通常采用的是在內(nèi)部排序中，通常采用的是 。即：將兩個。即：將兩個位置相鄰的記錄有序子序列歸并為一個記錄有序的序列。位置相鄰的記錄有序子序列歸并為一個記錄有序的序列。 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 第七章第七章 內(nèi)部排序內(nèi)部排序 迭代的歸并排序算法迭代的歸并排序算法設(shè)設(shè)L0L0到到Ln-1Ln-1中中 n n 個記錄已經(jīng)分為一些長度為個記錄已經(jīng)分為一些長度為 lenl

44、en的歸并項，將這些歸并項兩兩歸并，歸并成長度的歸并項，將這些歸并項兩兩歸并，歸并成長度為為2 2lenlen的歸并項的歸并項, , 結(jié)果放到結(jié)果放到L1 L1 中。中。如果如果n n 不是不是2 2lenlen的整數(shù)倍，則一趟歸并到最后，的整數(shù)倍，則一趟歸并到最后，可能遇到兩種情形：可能遇到兩種情形： 剩下一個長度為剩下一個長度為lenlen的歸并項和另一個長度不的歸并項和另一個長度不足足lenlen的歸并項的歸并項，可用，可用mergemerge算法將它們歸并成算法將它們歸并成一個長度小于一個長度小于2 2* *lenlen的歸并項。的歸并項。(1)(1) 只剩下一個歸并項只剩下一個歸并項

45、，其長度小于或等于，其長度小于或等于len, len, 將將它直接抄到它直接抄到L1 L1 中。中。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 第七章第七章 內(nèi)部排序內(nèi)部排序 void MergePass (dataList& L, dataList& L1, int len) int i = 0; /循環(huán)兩兩歸并：兩個子序列長度相等/處理一個長度為len的歸并項和另一個長度不足len的歸并項/處理只剩下一個歸并項，其長度小于或等于len, 直接抄到L1 中。 while (i+2*len-1 = L.n-1) /批量處理批量處理 merge(L, L1, i, i+len-1, i+2*len-1);

46、 i = i+2*len; if (i+len = L.n-1) merge(L, L1, i, i+len-1, L.n-1);else for (int j = i; j = L.n-1; j+) L1.Vj = L.Vj; L1.n = L.n;數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 第七章第七章 內(nèi)部排序內(nèi)部排序 ( (兩路兩路) )歸并排序的主算法歸并排序的主算法void MergeSort (dataList& L) /按記錄關(guān)鍵字值非遞減的順序?qū)Ρ碇杏涗浥判?dataList L1; /設(shè)置輔助表 int len = 1; while (len n) MergePass (L, L1, len

47、); len = 2*len; MergePass (L1, L, len); len = 2*len; 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 第七章第七章 內(nèi)部排序內(nèi)部排序 在迭代的歸并排序算法中，MergePass 做一趟兩路歸并排序, 要調(diào)用merge 函數(shù) n/(2*len) O(n/len)次；MergeSort 調(diào)用MergePass 正好 loglog2 2n n 次；每次merge()要執(zhí)行比較O(len)。所以算法總的時間復(fù)雜度為O(nlogO(nlog2 2n)n)。 歸并排序需要另外一個與原待排序記錄數(shù)組同樣大小的輔助數(shù)組，占用附加存儲較多。 歸并排序是一個穩(wěn)定穩(wěn)定的排序方法。算法分析數(shù)據(jù)結(jié)

48、構(gòu)數(shù)據(jù)結(jié)構(gòu) 第七章第七章 內(nèi)部排序內(nèi)部排序 7.7 基數(shù)排序基數(shù)排序 基數(shù)排序是一種借助基數(shù)排序是一種借助“”的思想來實現(xiàn)的思想來實現(xiàn)“單關(guān)單關(guān)鍵鍵 字排序字排序”的內(nèi)部排序算法。的內(nèi)部排序算法。 7.7.1 多關(guān)鍵字的排序多關(guān)鍵字的排序 例：例：將右表所示的學(xué)生將右表所示的學(xué)生 成績單按數(shù)學(xué)成績成績單按數(shù)學(xué)成績 的等級由高到低排的等級由高到低排 序，數(shù)學(xué)成績相同序，數(shù)學(xué)成績相同 的學(xué)生再按英語成的學(xué)生再按英語成 績的高低等級排序?？兊母叩偷燃壟判颉?學(xué)號學(xué)號數(shù)學(xué)數(shù)學(xué)英語英語其它其它 101 B C 102 A B 103 C D 104 B B 105 A A 106 D B 107 E A

49、 108 C B105 A A 102 A B 104 B B 101 B C 108 C B 103 C D 106 D B 107 E A特點(diǎn)：特點(diǎn)：每個記錄最終的每個記錄最終的 位置由兩個關(guān)鍵位置由兩個關(guān)鍵 字字 k1 k2 決定。決定。 第二關(guān)鍵字第二關(guān)鍵字 K2 第一關(guān)鍵字第一關(guān)鍵字 K1 我們將它稱之為我們將它稱之為，即，即多關(guān)鍵字多關(guān)鍵字 排序是按照復(fù)合關(guān)鍵字排序是按照復(fù)合關(guān)鍵字 的大小排序的大小排序。 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 第七章第七章 內(nèi)部排序內(nèi)部排序 例：例：撲克牌中撲克牌中 52 張牌，可按張牌，可按和和分成兩個分成兩個“關(guān)鍵字關(guān)鍵字”，其，其 大小關(guān)系為：花色：大小關(guān)系為：

50、花色： 面值：面值： 2345678910JQKA 若對撲克牌按花色、面值進(jìn)行升序排序，得到如下序列：若對撲克牌按花色、面值進(jìn)行升序排序，得到如下序列： 2, 3, ., A, 2, 3, ., A, 2, 3, ., A, 2, 3, ., A 即兩張牌，若花色不同，不論面值怎樣，花色低的那張牌小即兩張牌，若花色不同，不論面值怎樣，花色低的那張牌小 于花色高的，只有在同花色情況下，大小關(guān)系才由面值的大小確于花色高的，只有在同花色情況下，大小關(guān)系才由面值的大小確 定。這也是定。這也是按照復(fù)合關(guān)鍵字的大小排序，按照復(fù)合關(guān)鍵字的大小排序，即：即：。 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 第七章第七章 內(nèi)部排序內(nèi)部排序

51、 多關(guān)鍵字排序的方法：多關(guān)鍵字排序的方法： 多關(guān)鍵字排序按照從最主位關(guān)鍵字到最次位關(guān)鍵多關(guān)鍵字排序按照從最主位關(guān)鍵字到最次位關(guān)鍵字或從最次字或從最次 位關(guān)鍵字到最主位關(guān)鍵字的順序逐次排位關(guān)鍵字到最主位關(guān)鍵字的順序逐次排序，分兩種方法：序，分兩種方法： 最高位優(yōu)先法，簡稱最高位優(yōu)先法，簡稱 MSD 法：法：先按先按 k 0 排序分組，同一組中排序分組，同一組中 記錄，關(guān)鍵字記錄，關(guān)鍵字 k 0 相等，再對各組按相等，再對各組按 k 1 排序分成子組，之后，對排序分成子組，之后，對 后面的關(guān)鍵字繼續(xù)這樣的排序分組，直到按最次位關(guān)鍵字后面的關(guān)鍵字繼續(xù)這樣的排序分組，直到按最次位關(guān)鍵字 k d 對對

52、各子組排序后，再將各組連接起來，便得到一個有序序列。各子組排序后，再將各組連接起來，便得到一個有序序列。 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 第七章第七章 內(nèi)部排序內(nèi)部排序 3,1,201,2,152,3,181,2,15 無序序列無序序列 3,2,30 最低位優(yōu)先法，簡稱最低位優(yōu)先法，簡稱 LSD 法：法：先從先從 k d-1 開始排序，再對開始排序，再對 k d-2 進(jìn)行排序，依次重復(fù)，直到對進(jìn)行排序，依次重復(fù)，直到對 k 0 排序后便得到一個有序序列。排序后便得到一個有序序列。 例：例：學(xué)生記錄含三個關(guān)鍵字：學(xué)生記錄含三個關(guān)鍵字： 系別系別、和和班內(nèi)的序列號班內(nèi)的序列號， 其中以系別為最主位關(guān)鍵字。其中以

53、系別為最主位關(guān)鍵字。對對K2排序排序 對對K1排序排序 對對K0排序排序 3,1,202,1,202,3,183,1,20 2,1,203,2,302,1,201,2,153,2,302,3,18 1,2,152,1,202,3,183,1,203,2,30LSD的排序過程如下：的排序過程如下： 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 第七章第七章 內(nèi)部排序內(nèi)部排序 例例：先將學(xué)生記錄按：先將學(xué)生記錄按英語英語等級由高到低分成等級由高到低分成 A、B、C、D、E 五五 個組：個組： 關(guān)鍵字類別關(guān)鍵字類別 ABCDE各組成員各組成員 AAABBCCDEABBDBCB學(xué)號學(xué)號數(shù)學(xué)數(shù)學(xué)英語英語其它其它 101 B C 1

54、02 A B 103 C D 104 B B 105 A A 106 D B 107 E A 108 C B然后按從左向右，從上向下的順序?qū)⑷缓蟀磸淖笙蛴?，從上向下的順序?qū)?它們收集起來得到關(guān)鍵字序列：它們收集起來得到關(guān)鍵字序列： AA，EA，AB，BB，DB，CB，BC，CD 用用 LSD 法進(jìn)行的排序，在一定的條件下（即對法進(jìn)行的排序，在一定的條件下（即對 Ki 的不同值的不同值 Ki+1 均取相同值），可通過若干次均取相同值），可通過若干次“分配分配”和和“收集收集”來實現(xiàn)。來實現(xiàn)。 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 第七章第七章 內(nèi)部排序內(nèi)部排序 再按數(shù)學(xué)成績由高到低分成再按數(shù)學(xué)成績由高到低分成 A、

55、B、C、D、E 五個組：五個組： 關(guān)鍵字類別關(guān)鍵字類別 ABCDE各組成員各組成員 AAABBCCDEABBDBCB關(guān)鍵字類別關(guān)鍵字類別 ABCDE各組成員各組成員 AABBCBDBEAABBCCD 可以看出，這個關(guān)鍵字序列已經(jīng)是有序的了?？梢钥闯?，這個關(guān)鍵字序列已經(jīng)是有序的了。 對每個關(guān)鍵字都是將整個序列按關(guān)鍵字分組，然后按順序收對每個關(guān)鍵字都是將整個序列按關(guān)鍵字分組，然后按順序收 集，顯然集，顯然LSD法，操作比較簡單。法，操作比較簡單。按從上向下，從左向按從上向下，從左向 右的順序?qū)⑵涫占鹩业捻樞驅(qū)⑵涫占?來得到關(guān)鍵字序列：來得到關(guān)鍵字序列： AA，EA，AB，BB， DB，CB，B

56、C，CD 按從上向下，從左向按從上向下，從左向右的順序?qū)⑵涫占鹩业捻樞驅(qū)⑵涫占?來得到關(guān)鍵字序列：來得到關(guān)鍵字序列： 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 第七章第七章 內(nèi)部排序內(nèi)部排序 MSD 與與 LSD 的的不同特點(diǎn)不同特點(diǎn) 必須將序列逐層分必須將序列逐層分 割成若干子序列，割成若干子序列， 然后對各子序列分然后對各子序列分 別排序。別排序。 不必分成子序列，不必分成子序列， 對每個關(guān)鍵字都是對每個關(guān)鍵字都是 整個序列參加排序；整個序列參加排序； 通過若干次分配與通過若干次分配與 收集實現(xiàn)排序。收集實現(xiàn)排序。 LSD MSD 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 第七章第七章 內(nèi)部排序內(nèi)部排序 基數(shù)排序：基數(shù)排序： 是借助

57、于多關(guān)鍵字排序思想進(jìn)行排序的一種排序方法。該是借助于多關(guān)鍵字排序思想進(jìn)行排序的一種排序方法。該 方法將排序關(guān)鍵字方法將排序關(guān)鍵字K 看作是由多個關(guān)鍵字組成的組合關(guān)鍵字，看作是由多個關(guān)鍵字組成的組合關(guān)鍵字， 即：即：K=k0k1kd-1。每個關(guān)鍵字。每個關(guān)鍵字 ki 表示關(guān)鍵字的一位，其中表示關(guān)鍵字的一位，其中 k0 為最高位，為最高位，kd-1 為最低位，為最低位，d 為關(guān)鍵字的位數(shù)。為關(guān)鍵字的位數(shù)。 例：例：對于關(guān)鍵字序列對于關(guān)鍵字序列 (101, 203, 567, 231, 478, 352)，可以將每個，可以將每個 關(guān)鍵字關(guān)鍵字 K 看成由三個單關(guān)鍵字組成，即看成由三個單關(guān)鍵字組成，即

58、 K= k1k2k3， 每個關(guān)鍵字每個關(guān)鍵字 的取值范圍為的取值范圍為 0ki9，所以每個關(guān)鍵字可取值的數(shù)目為，所以每個關(guān)鍵字可取值的數(shù)目為 10。 通常將關(guān)鍵字取值的數(shù)目稱為通常將關(guān)鍵字取值的數(shù)目稱為，用，用 r 表示，在本例中表示，在本例中 r =10。 對于關(guān)鍵字序列（對于關(guān)鍵字序列（AB, BD, ED）可以將每個關(guān)鍵字看成是）可以將每個關(guān)鍵字看成是 由二個單字母關(guān)鍵字組成的復(fù)合關(guān)鍵字，并且每個關(guān)鍵字的取由二個單字母關(guān)鍵字組成的復(fù)合關(guān)鍵字，并且每個關(guān)鍵字的取 值范圍為值范圍為 “AZ”，所以關(guān)鍵字的基數(shù)，所以關(guān)鍵字的基數(shù) r = 26。 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 第七章第七章 內(nèi)部排序內(nèi)部排序

59、 基數(shù)排序可用多關(guān)鍵字的基數(shù)排序可用多關(guān)鍵字的LSD方法排序，即對待排序的記方法排序，即對待排序的記 錄序列按復(fù)合關(guān)鍵字從低位到高位的順序交替地進(jìn)行錄序列按復(fù)合關(guān)鍵字從低位到高位的順序交替地進(jìn)行“分組分組”、 “收集收集”，最終得到有序的記錄序列。在此我們將一次，最終得到有序的記錄序列。在此我們將一次“分分組組”、 “收集收集”稱為一趟。對于由稱為一趟。對于由 d 位關(guān)鍵字組成的復(fù)合關(guān)位關(guān)鍵字組成的復(fù)合關(guān)鍵字，需要經(jīng)過鍵字，需要經(jīng)過d 趟的趟的“分配分配”與與“收集收集”。 因此，若因此，若 d 值值較大，基數(shù)排序的時間效率就會隨之降低。較大，基數(shù)排序的時間效率就會隨之降低。 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)

60、 第七章第七章 內(nèi)部排序內(nèi)部排序 在計算機(jī)上實現(xiàn)基數(shù)排序時，為減少所需輔助存儲空間，在計算機(jī)上實現(xiàn)基數(shù)排序時，為減少所需輔助存儲空間， 應(yīng)采用鏈表作存儲結(jié)構(gòu)應(yīng)采用鏈表作存儲結(jié)構(gòu)，即鏈?zhǔn)交鶖?shù)排序，具體作法為：，即鏈?zhǔn)交鶖?shù)排序，具體作法為： 7.6.2 鏈?zhǔn)交鶖?shù)排序鏈?zhǔn)交鶖?shù)排序 1、以靜態(tài)鏈表存儲待排記錄，并令表頭指針指向第一個記錄；、以靜態(tài)鏈表存儲待排記錄，并令表頭指針指向第一個記錄； 2、“分配分配” 時，按當(dāng)前時，按當(dāng)前“關(guān)鍵字位關(guān)鍵字位”所取值，將記錄分配到不所取值，將記錄分配到不同的同的 “鏈隊列鏈隊列” 中，每個隊列中記錄的中，每個隊列中記錄的 “關(guān)鍵字位關(guān)鍵字位” 相同；相同； 3、“收集收集”時，按當(dāng)前關(guān)鍵字位取值從小到大將各隊列首尾相時，按當(dāng)前關(guān)鍵字位取值從小到大將各隊列首尾相 鏈成一