《數(shù)據(jù)結(jié)構(gòu)》C語言版第十章-內(nèi)部排序課件

1、10.1 概述10.2 插入排序10.3 快速排序10.4 選擇排序10.5 歸并排序10.6 基數(shù)排序10.7 各種排序方法的綜合比較第十章 內(nèi)部排序第1頁，共115頁。1. 了解排序的定義和各種排序方法的特點(diǎn)。2.熟悉各種方法的排序過程及其依據(jù)的原則。3. 掌握各種排序方法的時間復(fù)雜度的分析方法。能從“關(guān)鍵字間的比較次數(shù)”分析排序算法的平均情況和最壞情況的時間性能。4. 理解排序方法“穩(wěn)定”或“不穩(wěn)定”的含義，弄清楚在什么情況下要求應(yīng)用的排序方法必須是穩(wěn)定的。學(xué)習(xí)提要：第2頁，共115頁。重難點(diǎn)內(nèi)容： 直接插入排序、折半插入排序、起泡排序、簡單選擇排序等排序方法的算法思想、實(shí)現(xiàn)和效率分析。

2、 希爾排序、快速排序、堆排序、歸并排序等高效方法。第3頁，共115頁。10.1 概述一、什么是排序三、內(nèi)部排序的方法二、內(nèi)部排序和外部排序第4頁，共115頁。一、什么是排序？ 排序是計(jì)算機(jī)內(nèi)經(jīng)常進(jìn)行的一種操作，其目的是將一組“無序”的記錄序列調(diào)整為“有序”的記錄序列。例如：將下列關(guān)鍵字序列52, 49, 80, 36, 14, 58, 61, 23, 97, 75調(diào)整為14, 23, 36, 49, 52, 58, 61 ,75, 80, 97第5頁，共115頁。 一般情況下，假設(shè)含n個記錄的序列為 R1, R2, ， Rn 其相應(yīng)的關(guān)鍵字序列為 K1, K2, ，Kn 這些關(guān)鍵字相互之間可以

3、進(jìn)行比較，即在它們之間存在著這樣一個關(guān)系 ： Kp1Kp2Kpn按此固有關(guān)系將上式記錄序列重新排列為 Rp1, Rp2, ，Rpn 的操作稱作排序。第6頁，共115頁。 假設(shè)Ki=Kj (1i,jn,i j)，且在排序前的序列中Ri領(lǐng)先于Rj（即ij）。 若排序后的序列中Ri仍領(lǐng)先于Rj，則稱所用的排序方法是穩(wěn)定的； 反之，若可能排序后的序列中Rj領(lǐng)先于Ri，則稱使用的排序方法是不穩(wěn)定的。第7頁，共115頁。例如：（14, 36, 49, 49, 52, 80）排序后（52, 49, 80, 36, 14, 49）排序前（14, 36, 49, 49, 52, 80）穩(wěn)定不穩(wěn)定第8頁，共115

4、頁。二、內(nèi)部排序和外部排序若整個排序過程不需要訪問外存便能完成，則稱此類排序問題為內(nèi)部排序； 反之，若參加排序的記錄數(shù)量很大， 整個序列的排序過程不可能在內(nèi)存中 完成，則稱此類排序問題為外部排序。第9頁，共115頁。三、內(nèi)部排序的方法內(nèi)部排序的過程是一個逐步擴(kuò)大記錄的有序序列長度的過程。經(jīng)過一趟排序有序序列區(qū)無 序 序 列 區(qū)有序序列區(qū)無 序 序 列 區(qū)第10頁，共115頁?；诓煌摹皵U(kuò)大” 有序序列長度的方法，內(nèi)部排序方法大致可分下列幾種類型：插入類交換類選擇類 歸并類其它方法第11頁，共115頁。1. 插入類將無序子序列中的一個或幾個記錄“插入”到有序序列中，從而增加記錄的有序子序列的長

5、度。第12頁，共115頁。2. 交換類通過“交換”無序序列中的記錄從而得到其中關(guān)鍵字最小或最大的記錄，并將它加入到有序子序列中，以此方法增加記錄的有序子序列的長度。第13頁，共115頁。3. 選擇類從記錄的無序子序列中“選擇”關(guān)鍵字最小或最大的記錄，并將它加入到有序子序列中，以此方法增加記錄的有序子序列的長度。第14頁，共115頁。4. 歸并類通過“歸并”兩個或兩個以上的記錄有序子序列，逐步增加記錄有序序列的長度。5. 其它方法第15頁，共115頁。待排記錄的數(shù)據(jù)類型定義如下:#define MAXSIZE 1000 / 待排順序表最大長度typedef int KeyType; / 關(guān)鍵字類

6、型為整數(shù)類型typedef struct KeyType key; / 關(guān)鍵字項(xiàng) InfoType otherinfo; / 其它數(shù)據(jù)項(xiàng) RcdType; / 記錄類型typedef struct RcdType rMAXSIZE+1; / r0閑置 int length; / 順序表長度 SqList; / 順序表類型第16頁，共115頁。10.2 插入排序一、直接插入排序三、表插入排序二、折半插入排序四、希爾（Shell）排序第17頁，共115頁。有序序列R1.i-1Ri無序序列 Ri.n一趟插入排序的基本思想：有序序列R1.i無序序列 Ri+1.n第18頁，共115頁。實(shí)現(xiàn)“一趟插入排序

7、”可分三步進(jìn)行：3將Ri 插入(復(fù)制)到Rj+1的位置上。2將Rj+1.i-1中的所有記錄均后移 一個位置；1在R1.i-1中查找Ri的插入位置， R1.j.key Ri.key Rj+1.i-1.key；第19頁，共115頁。一、直接插入排序利用 “順序查找”實(shí)現(xiàn)“在R1.i-1中查找Ri的插入位置”算法的實(shí)現(xiàn)要點(diǎn)：第20頁，共115頁。從Ri-1起向前進(jìn)行順序查找， 監(jiān)視哨設(shè)置在R0；R0 = Ri; / 設(shè)置“哨兵”循環(huán)結(jié)束表明Ri的插入位置為 j +1R0jRifor (j=i-1; R0.keyRj.key; -j); / 從后往前找j=i-1插入位置第21頁，共115頁。 對于在查

8、找過程中找到的那些關(guān)鍵字不小于Ri.key的記錄，并在查找的同時實(shí)現(xiàn)記錄向后移動；for (j=i-1; R0.keyRj.key; -j); Rj+1 = RjR0jRij= i-1上述循環(huán)結(jié)束后可以直接進(jìn)行“插入”插入位置第22頁，共115頁。第三趟排序后： （38，49，56）40，95例：待排序序列 （56，38，49，40，95）jijj404038495695key013245R564940第四趟排序后： （38，40，49，56）95第23頁，共115頁。令 i = 2，3，, n, 實(shí)現(xiàn)整個序列的排序。for ( i=2; i=n; +i ) if (Ri.keyRi-1.ke

9、y) 在 R1.i-1中查找Ri的插入位置; 插入Ri ; 第24頁，共115頁。void InsertionSort ( SqList &L ) / 對順序表 L 作直接插入排序。 for ( i=2; i=L.length; +i ) if (L.ri.key L.ri-1.key) / InsertSortL.r0 = L.ri; / 復(fù)制為監(jiān)視哨L.ri = L.ri-1;for ( j=i-2; L.r0.key L.rj.key; - j ) L.rj+1 = L.rj; / 記錄后移L.rj+1 = L.r0; / 插入到正確位置第25頁，共115頁。內(nèi)部排序的時間分析：實(shí)現(xiàn)內(nèi)部

10、排序的基本操作有兩個：（2）“移動”記錄。（1）“比較”序列中兩個關(guān)鍵字的 大?。坏?6頁，共115頁。對于直接插入排序：最好的情況（關(guān)鍵字在記錄序列中順序有序）：“比較”的次數(shù)：最壞的情況（關(guān)鍵字在記錄序列中逆序有序）：“比較”的次數(shù)：0“移動”的次數(shù)：“移動”的次數(shù)：T(n)=O(n)穩(wěn)定的第27頁，共115頁。 因?yàn)?R1.i-1 是一個按關(guān)鍵字有序的有序序列，則可以利用折半查找實(shí)現(xiàn)“在R1.i-1中查找Ri的插入位置”，如此實(shí)現(xiàn)的插入排序?yàn)檎郯氩迦肱判?。二、折半插入排序?8頁，共115頁。void BiInsertionSort ( SqList &L ) / BInsertSort

11、在 L.r1.i-1中折半查找插入位置；for ( i=2; i=high+1; -j ) L.rj+1 = L.rj; / 記錄后移L.rhigh+1 = L.r0; / 插入第29頁，共115頁。low = 1; high = i-1;while (low=high) m = (low+high)/2; / 折半if (L.r0.key L.rm.key) high = m-1; / 插入點(diǎn)在低半?yún)^(qū)else low = m+1; / 插入點(diǎn)在高半?yún)^(qū)第30頁，共115頁。ilowhighmmlowlowmhighilowhighmhighmhighmlow例如:再如:插入位置插入位置14 3

12、6 49 52 8058 61 23 97 75L.r14 36 49 52 58 61 80 23 97 75L.r第31頁，共115頁。折半插入排序時間分析：時間復(fù)雜度： 折半插入排序比直接插入排序明顯地減少了關(guān)鍵字間的“比較”次數(shù)，但記錄“移動”的次數(shù)不變。 T(n)=O(n)空間復(fù)雜度：S(n)=O(1)穩(wěn)定的第32頁，共115頁。三、表插入排序 為了減少在排序過程中進(jìn)行的“移動”記錄的操作，必須改變排序過程中采用的存儲結(jié)構(gòu)。利用靜態(tài)鏈表進(jìn)行排序，并在排序完成之后，一次性地調(diào)整各個記錄相互之間的位置，即將每個記錄都調(diào)整到它們所應(yīng)該在的位置上。第33頁，共115頁。#define SIZ

13、E 100 /靜態(tài)鏈表容量Typedef struct /表結(jié)點(diǎn)類型 RcdType rc; /記錄項(xiàng) int next; /指針項(xiàng)SLNode;Typedef struct /靜態(tài)鏈表類型 SLNode rSIZE; /0號單元為表頭結(jié)點(diǎn) int length; /鏈表當(dāng)前長度SLinkListType;例如：第34頁，共115頁。void LInsertionSort (Elem SL ， int n) / 對記錄序列SL1.n作表插入排序 SL0.key = MAXINT ; SL0.next = 1; SL1.next = 0; for ( i=2; i=n; +i ) for ( j

14、=0, k = SL0.next;SLk.key= SLi.key ; j=k, k=SLk.next ) SLj.next = i; SLi.next = k; / 結(jié)點(diǎn)i插入在結(jié)點(diǎn)j和結(jié)點(diǎn)k之間/ LinsertionSort第35頁，共115頁。算法中使用了三個指針：其中：p指示第i個記錄的當(dāng)前位置 i指示第i個記錄應(yīng)在的位置 q指示第i+1個記錄的當(dāng)前位置如何在排序之后調(diào)整記錄序列？例如：第36頁，共115頁。void Arrange ( SLinkListType &SL, int n ) p = SL.r0.next; / p指示第一個記錄的當(dāng)前位置 for ( i=1; in;

15、+i ) while (pi) p = SL.rp.next; q = SL.rp.next; / q指示尚未調(diào)整的表尾 if ( p!= i ) SL.rpSL.ri; / 交換記錄，使第i個記錄到位 SL.ri.next = p; / 指向被移走的記錄 p = q; / p指示尚未調(diào)整的表尾， / 為找第i+1個記錄作準(zhǔn)備 / Arrange第37頁，共115頁。表插入排序時間分析： 從表插入排序的過程可見，它的基本操作仍是將一個記錄插入到已排好序的有序表中。和直接插入排序相比，不同之處是用修改2n次指針值代替移動記錄，但比較次數(shù)相同。T(n) = O(n 2) 重排記錄的過程，最壞的情況

16、是每個記錄到位都必須進(jìn)行一次交換，即移動3(n-1)次。穩(wěn)定的第38頁，共115頁。 四、希爾排序（又稱縮小增量排序） 基本思想：對待排記錄序列先作“宏觀”調(diào)整，再作“微觀”調(diào)整。 所謂“宏觀”調(diào)整，指的是，“跳躍式”的插入排序。 具體做法為：第39頁，共115頁。 將記錄序列分成若干子序列，分別對每個子序列進(jìn)行插入排序。 其中，d 稱為增量，它的值在排序過程中從大到小逐漸縮小，直至最后一趟排序減為 1。例如：將 n 個記錄分成 d 個子序列： R1，R1+d，R1+2d，R1+kd R2，R2+d，R2+2d，R2+kd Rd，R2d，R3d，Rkd，R(k+1)d 第40頁，共115頁。1

17、6 25 12 30 47 11 23 36 9 18 31 例如： 第一趟希爾排序，設(shè)增量 d =511 23 12 9 18 16 25 36 30 47 31 第二趟希爾排序，設(shè)增量 d = 39 18 12 11 23 16 25 31 30 47 36第三趟希爾排序，設(shè)增量 d = 1 9 11 12 16 18 23 25 30 31 36 47 1 2 3 4 5 6 7 8 9 10 11第41頁，共115頁。void ShellInsert ( SqList &L, int dk ) for ( i=dk+1; i=n; +i ) if ( L.ri.key0&(L.r0.k

18、eyL.rj.key); j-=dk) L.rj+dk = L.rj; / 記錄后移，查找插入位置 L.rj+dk = L.r0; / 插入 / if / ShellInsert第42頁，共115頁。void ShellSort (SqList &L, int dlta, int t) / 增量為dlta的希爾排序 for (k=0; k1 & flag=1; - i ) flag=0; for (j=1; jL.rj+1.key) flag=1; x=L.rj; L.rj=L.rj+1; L.rj+1=x; 結(jié)束條件為: 最后一趟沒有進(jìn)行“交換記錄”。第49頁，共115頁。起泡排序時間分析:

19、最好的情況（關(guān)鍵字在記錄序列中順序有序）： 只需進(jìn)行一趟起泡“比較”的次數(shù)：最壞的情況（關(guān)鍵字在記錄序列中逆序有序）： 需進(jìn)行n-1趟起泡“比較”的次數(shù)：0“移動”的次數(shù)：“移動”的次數(shù)：n-1穩(wěn)定的第50頁，共115頁。 從起泡排序的過程可見，起泡排序是一個增加有序序列長度的過程，也是一個縮小無序序列長度的過程，每經(jīng)過一趟起泡，無序序列的長度只縮小1。 試設(shè)想，若能在經(jīng)過一趟排序，使無序序列的長度縮小一半，則必能加快排序的速度。 第51頁，共115頁。二、一趟快速排序（一次劃分）目標(biāo)：找一個記錄，以它的關(guān)鍵字作為“樞軸”，凡其關(guān)鍵字小于樞軸的記錄均移動至該記錄之前，反之，凡關(guān)鍵字大于樞軸的記

20、錄均移動至該記錄之后。 致使一趟排序之后，記錄的無序序列L.r s.t將分割成兩部分: L.r s.i-1和L.r i+1.t，且 L.rj.key L.r i.key L.r j.key (sji-1) 樞軸 (i+1jt)。第52頁，共115頁。p例初始關(guān)鍵字： 49 38 65 97 76 13 27 50 lhh 完成一趟排序： ( 27 38 13) 49 (76 97 65 50) 分別進(jìn)行快速排序: ( 13) 27 (38) 49 (50 65) 76 (97) 快速排序結(jié)束： 13 27 38 49 50 65 76 974927lll4965h1349h4997h第53頁，

21、共115頁。int Partition (SqList &L, int low, int high) pivotkey = L.rlow.key; while (lowhigh) while (low=pivotkey) -high; L.rlow L.rhigh; while (lowhigh & L.rlow.key=pivotkey) +low; L.rlow L.rhigh; return low; / 返回樞軸所在位置 / Partition第54頁，共115頁。int Partition (SqList &L, int low, int high) / Partition L.r0

22、 = L.rlow; pivotkey=L.rlow.key; / 樞軸 while (lowhigh) while(low=pivotkey) - high; / 從右向左搜索L.rlow = L.rhigh;while (lowhigh & L.rlow.key=pivotkey) + low; / 從左向右搜索L.rhigh = L.rlow;L.rlow = L.r0; return low;第55頁，共115頁。三、快速排序 首先對無序的記錄序列進(jìn)行“一次劃分”，之后分別對分割所得兩個子序列“遞歸”進(jìn)行快速排序。無 序 的 記 錄 序 列無序記錄子序列(1)無序子序列(2)樞軸一次劃

23、分分別進(jìn)行快速排序第56頁，共115頁。void QSort (SqList &L, int low, int high ) / 對順序表L中子序列L.rlow.high作快速排序 if (low high) / 長度大于1 / QSort pivotloc = Partition(L, low, high); / 對 L.rlow.high進(jìn)行一次劃分 QSort(L, low, pivotloc-1); / 對低子序列遞歸排序，pivotloc是樞軸位置 QSort(L, pivotloc+1, high); / 對高子序列遞歸排序第57頁，共115頁。void QuickSort( Sq

24、List & L) / 對順序表進(jìn)行快速排序 QSort(L, 1, L.length); / QuickSort 第一次調(diào)用函數(shù) Qsort 時，待排序記錄序列的上、下界分別為 1 和 L.length。第58頁，共115頁?？焖倥判虻臅r間分析:假設(shè)一次劃分所得樞軸位置 i=k，則對n 個記錄進(jìn)行快排所需時間：其中 Tpass(n)為對 n 個記錄進(jìn)行一次劃分所需時間。 若待排序列中記錄的關(guān)鍵字是隨機(jī)分布的，則 k 取 1 至 n 中任意一值的可能性相同。T(n) = Tpass(n) + T(k-1) + T(n-k)第59頁，共115頁。設(shè) Tavg(1)b則可得結(jié)果：結(jié)論: 快速排序的

25、時間復(fù)雜度為O(nlogn)由此可得快速排序所需時間的平均值為：不穩(wěn)定的第60頁，共115頁。 若待排記錄的初始狀態(tài)為按關(guān)鍵字有序時，快速排序?qū)⑼懟癁槠鹋菖判?，其時間復(fù)雜度為O(n2)。 為避免出現(xiàn)這種情況，需在進(jìn)行一次劃分之前，進(jìn)行“予處理”，即： 先對 L.rlow.key, L.rhigh.key和 L.r (low+high)/2.key，進(jìn)行相互比較，然后取關(guān)鍵字為 “三者之中”的記錄為樞軸記錄。第61頁，共115頁。10.4 選擇排序一、簡單選擇排序三、堆排序二、樹型選擇排序第62頁，共115頁。一、簡單選擇排序假設(shè)排序過程中，待排記錄序列的狀態(tài)為：有序序列R1.i-1無序序列 R

26、i.n 第 i 趟簡單選擇排序從中選出關(guān)鍵字最小的記錄有序序列R1.i無序序列 Ri+1.n第63頁，共115頁。void SelectSort (SqList &L, int n ) / 對記錄序列R1.n作簡單選擇排序。 for (i=1; iL.length; +i) / 選擇第 i 小的記錄，并交換到位 / SelectSortj = SelectMinKey(L, i); / 在 Ri.n 中選擇關(guān)鍵字最小的記錄if (i!=j) L.riL.rj; / 與第 i 個記錄交換第64頁，共115頁。例初始： 49 38 65 97 76 13 27 jkkkkkkjji=11349一趟

27、： 13 38 65 97 76 49 27 i=2jjkkkkk2738二趟： 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é)束： 13 27 38 49 65 76 97第65頁，共115頁。時間性能分析： 對 n 個記錄進(jìn)行簡單選擇排序，所需進(jìn)行的 關(guān)鍵字間的比較次數(shù) 總計(jì)為：移動記錄的次數(shù)，最小值為 0, 最大值為3(n-1) 。不穩(wěn)定的第66頁，共115頁。三、堆排序堆是滿足下列性質(zhì)的

28、數(shù)列k1, k2, ,kn：或堆的定義:12, 36, 27, 65, 40, 34, 98, 81, 73, 55, 49例如:是小頂堆12, 36, 27, 65, 40, 14, 98, 81, 73, 55, 49不是堆(小頂堆)(大頂堆)第67頁，共115頁。kik2i k2i+1 若將該數(shù)列視作完全二叉樹，則 k2i 是 ki 的左孩子； k2i+1 是 ki 的右孩子。1236276549817355403498例如:是堆14不第68頁，共115頁。 將無序序列建成一個堆，得到關(guān)鍵字最?。ɑ蜃畲螅┑挠涗?；輸出堆頂?shù)淖钚。ù螅┲岛?，使剩余的n-1個元素重又建成一個堆，則可得到n個元

29、素的次小值；重復(fù)執(zhí)行，得到一個有序序列，這個過程叫堆排序。 堆排序即是利用堆的特性對記錄序列進(jìn)行排序的一種排序方法。第69頁，共115頁。例如：建大頂堆 98, 81, 49, 73, 36, 27, 40, 55, 64, 12 12, 81, 49, 73, 36, 27, 40, 55, 64, 98 交換 98 和 12重新調(diào)整為大頂堆 81, 73, 49, 64, 36, 27, 40, 55, 12, 98 40, 55, 49, 73, 12, 27, 98, 81, 64, 36 第70頁，共115頁。（1）如何由一個無序序列建成一個堆？堆排序需解決的兩個問題:（2）如何在輸

30、出堆頂元素之后，調(diào)整剩余元素使之成為一個新的堆？第71頁，共115頁。 輸出堆頂元素之后，以堆中最后一個元素替代之；然后將根結(jié)點(diǎn)值與左、右子樹的根結(jié)點(diǎn)值進(jìn)行比較，并與其中小者（或大者）進(jìn)行交換；重復(fù)上述操作，直至葉子結(jié)點(diǎn)，將得到新的堆，稱這個從堆頂至葉子的調(diào)整過程為“篩選”。第二個問題解決方法篩選:第72頁，共115頁。98814973556412362740例如:是大頂堆1298128173641298比較比較第73頁，共115頁。void HeapAdjust (RcdType &H, int s, int m) / 已知 H.rs.m中記錄的關(guān)鍵字除 H.rs 之外均 / 滿足堆的特征，

31、本函數(shù)自上而下調(diào)整 H.rs 的 / 關(guān)鍵字，使 H.rs.m 也成為一個大頂堆。 / HeapAdjustrc = H.rs; / 暫存 H.rs for ( j=2*s; j= H.rj.key ) break; / 再作“根”和“子樹根”之間的比較， / 若“=”成立，則說明已找到 rc 的插 / 入位置 s ，不需要繼續(xù)往下調(diào)整H.rs = H.rj; s = j; / 否則記錄上移，尚需繼續(xù)往下調(diào)整if ( jm & H.rj.key0; -i ) HeapAdjust ( H.r, i, H.length ); / 建大頂堆for ( i=H.length; i1; -i ) H.

32、r1H.ri; / 將堆頂記錄和當(dāng)前未經(jīng)排序子序列 / H.r1.i中最后一個記錄相互交換 HeapAdjust(H.r, 1, i-1); / 對 H.r1 進(jìn)行篩選第78頁，共115頁。堆排序的時間復(fù)雜度分析：1. 對深度為 k 的堆，“篩選”所需進(jìn)行的關(guān)鍵字比較的次數(shù)至多為2(k-1)；3. 調(diào)整“堆頂” n-1 次，總共進(jìn)行的關(guān)鍵 字比較的次數(shù)不超過 2 (log2(n-1)+ log2(n-2)+log22) 2n(log2n) 因此，堆排序的時間復(fù)雜度為O(nlogn)。2. 對 n 個關(guān)鍵字，建成深度為h(=log2n+1)的堆，所需進(jìn)行的關(guān)鍵字比較的次數(shù)至多 4n；不穩(wěn)定的第7

33、9頁，共115頁。 歸并：將兩個或兩個以上的有序表組合成一個新的有序表。10.5 歸并排序第80頁，共115頁。在內(nèi)部排序中，通常采用的是2-路歸并排序。即：將兩個位置相鄰的記錄有序子序列歸并為一個記錄的有序序列。有 序 序 列 Rl.n有序子序列 Rl.m有序子序列 Rm+1.n這個操作對順序表而言，是輕而易舉的。第81頁，共115頁。例: 給定待排序序列（49,38,65,97,76,13,27）初始關(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 4

34、9 65 76 97第82頁，共115頁。void Merge (RcdType SR, RcdType &TR, int i, int m, int n) / 將有序的記錄序列 SRi.m 和 SRm+1.n / 歸并為有序的記錄序列 TRi.n / Mergefor (j=m+1, k=i; i=m & j=n; +k) / 將SR中記錄由小到大地并入TR if (SRi.key=SRj.key) TRk = SRi+; else TRk = SRj+; 第83頁，共115頁。if (i=m) TRk.n = SRi.m; / 將剩余的 SRi.m 復(fù)制到 TRif (j=n) TRk.n

35、 = SRj.n; / 將剩余的 SRj.n 復(fù)制到 TR第84頁，共115頁。歸并排序的算法：如果記錄無序序列 Rs.t 的兩部分 Rs.(s+t)/2 和 R(s+t)/2+1.t分別按關(guān)鍵字有序，則利用上述歸并算法很容易將它們歸并成整個記錄序列是一個有序序列。 由此，應(yīng)該先分別對這兩部分進(jìn)行 2-路歸并排序。第85頁，共115頁。例如：52, 23, 80, 36, 68, 14 (s=1, t=6) 52, 23, 80 36, 68, 14 52, 2380 52 23, 52 23, 52, 8036, 6814366836, 6814, 36, 68 14, 23, 36, 52

36、, 68, 80 23第86頁，共115頁。void Msort ( RcdType SR, RcdType &TR1, int s, int t ) / 將SRs.t 歸并排序?yàn)?TR1s.t if (s= =t) TR1s=SRs; else / Msort 第87頁，共115頁。m = (s+t)/2; / 將SRs.t平分為SRs.m和SRm+1.tMsort (SR, TR2, s, m); / 遞歸地將SRs.m歸并為有序的TR2s.mMsort (SR, TR2, m+1, t); /遞歸地SRm+1.t歸并為有序的TR2m+1.tMerge (TR2, TR1, s, m, t

37、); / 將TR2s.m和TR2m+1.t歸并到TR1s.t第88頁，共115頁。void MergeSort (SqList &L) / 對順序表 L 作2-路歸并排序 MSort(L.r, L.r, 1, L.length); / MergeSort容易看出，對 n 個記錄進(jìn)行歸并排序的時間復(fù)雜度為(nlogn)。即： 每一趟歸并的時間復(fù)雜度為 O(n)， 總共需進(jìn)行 log2n 趟。穩(wěn)定的第89頁，共115頁?；鶖?shù)排序是一種借助“多關(guān)鍵字排序”的思想來實(shí)現(xiàn)“單關(guān)鍵字排序”的內(nèi)部排序算法。10.6.1 多關(guān)鍵字的排序10.6.2 鏈?zhǔn)交鶖?shù)排序10.6 基數(shù)排序第90頁，共115頁。例: 對

38、52張撲克牌按以下次序排序：23A23A23A23A兩個關(guān)鍵字：花色（ ） 面值（23A）并且“花色”地位高于“面值”。10.6.1 多關(guān)鍵字的排序第91頁，共115頁。 n 個記錄的序列 R1, R2, ，Rn對關(guān)鍵字 (Ki0, Ki1,Kid-1) 有序是指： 其中: K0 被稱為 “最主”位關(guān)鍵字Kd-1 被稱為 “最次”位關(guān)鍵字 對于序列中任意兩個記錄 Ri 和 Rj(1ijn) 都滿足下列(字典)有序關(guān)系： (Ki0, Ki1, ,Kid-1) (Kj0, Kj1, ,Kjd-1)第92頁，共115頁。 先對K0進(jìn)行排序，并按 K0 的不同值將記錄序列分成若干子序列之后，分別對 K

39、1 進(jìn)行排序，.， 依次類推，直至最后對最次位關(guān)鍵字排序完成為止。一、最高位優(yōu)先(MSD)法第93頁，共115頁。 先對 Kd-1 進(jìn)行排序，然后對 Kd-2 進(jìn)行排序，依次類推，直至對最主位關(guān)鍵字 K0 排序完成為止。 按LSD排序，不必分成子序列，對每個關(guān)鍵字都是整個序列參加排序；并且可不通過關(guān)鍵字比較，而通過若干次分配與收集實(shí)現(xiàn)排序。二、最低位優(yōu)先(LSD)法第94頁，共115頁。例如:學(xué)生記錄含三個關(guān)鍵字:系別、班號和班內(nèi)的序號，其中以系別為最主位關(guān)鍵字。 無序序列對K2排序?qū)1排序?qū)0排序3,2,301,2,153,1,202,3,182,1,201,2,152,3,183,1,

40、202,1,203,2,303,1,202,1,201,2,153,2,302,3,18 1,2,152,1,202,3,183,1,203,2,30LSD的排序過程如下:第95頁，共115頁。10.6.2 鏈?zhǔn)交鶖?shù)排序 假如多關(guān)鍵字的記錄序列中，每個關(guān)鍵字的取值范圍相同，則按LSD法進(jìn)行排序時，可以采用“分配-收集”的方法，其好處是不需要進(jìn)行關(guān)鍵字間的比較。 對于數(shù)字型或字符型的單關(guān)鍵字，可以看成是由多個數(shù)位或多個字符構(gòu)成的多關(guān)鍵字，此時可以采用這種“分配-收集”的辦法進(jìn)行排序，稱作基數(shù)排序法。第96頁，共115頁。例如：對下列這組關(guān)鍵字 209, 386, 768, 185, 247, 6

41、06, 230, 834, 539 首先按其 “個位數(shù)” 取值分別為 0, 1, , 9 “分配” 成 10 組，之后按從 0 至 9 的順序?qū)?它們 “收集” 在一起； 然后按其 “十位數(shù)” 取值分別為 0, 1, , 9 “分配” 成 10 組，之后再按從 0 至 9 的順序?qū)⑺鼈?“收集” 在一起； 最后按其“百位數(shù)”重復(fù)一遍上述操作。第97頁，共115頁。在計(jì)算機(jī)上實(shí)現(xiàn)基數(shù)排序時，為減少所需輔助存儲空間，應(yīng)采用鏈表作存儲結(jié)構(gòu)，即鏈?zhǔn)交鶖?shù)排序，具體作法為： 1. 待排序記錄以指針相鏈，構(gòu)成一個鏈表； 2. “分配” 時，按當(dāng)前“關(guān)鍵字位”所取值，將記錄分配到不同的 “鏈隊(duì)列” 中，每個隊(duì)

42、列中記錄的 “關(guān)鍵字位” 相同； 3. “收集”時，按當(dāng)前關(guān)鍵字位取值從小到大將各隊(duì)列首尾相鏈成一個鏈表;4. 對每個關(guān)鍵字位均重復(fù) 2) 和 3) 兩步。第98頁，共115頁。例初始狀態(tài)：278109063930589184505269008083109589269278063930083184505008e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9一趟分配930063083184505278008109589269一趟收集：第99頁，共115頁。505008109930063269278083184589二趟收集：08318458906350526993

43、0e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9二趟分配008109278930063083184505278008109589269一趟收集：第100頁，共115頁。008063083109184269278505589930三趟收集：109008184930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9三趟分配063083269278505589505008109930063269278083184589二趟收集：第101頁，共115頁。提醒注意：“分配”和“收集”的實(shí)際操作僅為修改鏈表中的指針和設(shè)置隊(duì)列的頭、尾指針；為查找使用，該鏈表尚需應(yīng)用算法Arrange 將它調(diào)整為有序表。第102頁，共115頁。 基數(shù)排序的時間復(fù)雜度為O(d(n+rd)其中：分配為O(n) 收集為O(rd)(rd為“基”) d為“分配-收集”的趟數(shù) 基數(shù)排序時間分析：第103頁，共115頁。10.7 各種排序方法的綜合比較一、時間性能三、排序方法的穩(wěn)定性能二、空間性能四、關(guān)于“排序方法的 時間復(fù)雜度的下限”第104頁，共115頁。一、時間性能1