數(shù)據(jù)結(jié)構(gòu)課程chap10,11排序ppt課件

1、第十章第十章排序排序10.1 概述概述10.2 插入排序插入排序10.3 快速排序快速排序10.4 堆排序堆排序10.5 歸并排序歸并排序10.6 基數(shù)排序基數(shù)排序10.7 各種排序方法的綜合比較各種排序方法的綜合比較10.8 外部排序外部排序10.1 概概 述述一、排序的定義一、排序的定義二、內(nèi)部排序和外部排序二、內(nèi)部排序和外部排序三、內(nèi)部排序方法的分類三、內(nèi)部排序方法的分類一、什么是排序？一、什么是排序？排序是計(jì)算機(jī)內(nèi)經(jīng)常進(jìn)展的一種操作，其目的是將一組“無序的記錄序列調(diào)整為“有序的記錄序列。例如：將以下關(guān)鍵字序列52, 49, 80, 36, 14, 58, 61, 23, 97, 75調(diào)

2、整為14, 23, 36, 49, 52, 58, 61 ,75, 80, 97 普通情況下，假設(shè)含n個(gè)記錄的序列為 R1, R2, ， Rn 其相應(yīng)的關(guān)鍵字序列為 K1, K2, ，Kn 這些關(guān)鍵字相互之間可以進(jìn)展比較，即在它們之間存在著這樣一個(gè)關(guān)系 ： Kp1Kp2Kpn按此固有關(guān)系將上式記錄序列重新陳列為 Rp1, Rp2, ，Rpn 的操作稱作排序。二、內(nèi)部排序和外部排序二、內(nèi)部排序和外部排序假設(shè)整個(gè)排序過程不需求訪問外存便能完成，那么稱此類排序問題為內(nèi)部排序； 反之，假設(shè)參與排序的記錄數(shù)量很大， 整個(gè)序列的排序過程不能夠在內(nèi)存中 完成，那么稱此類排序問題為外部排序。三、內(nèi)部排序的方法

3、三、內(nèi)部排序的方法內(nèi)部排序的過程是一個(gè)逐漸擴(kuò)展記錄的有序序列長(zhǎng)度的過程。經(jīng)過一趟排序經(jīng)過一趟排序有序序列區(qū)無 序 序 列 區(qū)有序序列區(qū)無 序 序 列 區(qū)基于不同的“擴(kuò)展 有序序列長(zhǎng)度的方法，內(nèi)部排序方法大致可分以下幾種類型：插入類插入類交換類交換類選擇類選擇類 歸并類歸并類其它方法其它方法待排記錄的數(shù)據(jù)類型定義如下待排記錄的數(shù)據(jù)類型定義如下:#define MAXSIZE 1000 / 待排順序表最大長(zhǎng)度待排順序表最大長(zhǎng)度typedef int KeyType; / 關(guān)鍵字類型為整數(shù)類型關(guān)鍵字類型為整數(shù)類型typedef struct KeyType key; / 關(guān)鍵字項(xiàng)關(guān)鍵字項(xiàng) InfoT

4、ype otherinfo; / 其它數(shù)據(jù)項(xiàng)其它數(shù)據(jù)項(xiàng) RcdType; / 記錄類型記錄類型typedef struct RcdType rMAXSIZE+1; / r0閑置閑置 int length; / 順序表長(zhǎng)度順序表長(zhǎng)度 SqList; / 順序表類型順序表類型1. 插入類插入類將無序子序列中的一個(gè)或幾個(gè)記錄“插入到有序序列中，從而添加記錄的有序子序列的長(zhǎng)度。2. 交換類交換類經(jīng)過“交換無序序列中的記錄從而得到其中關(guān)鍵字最小或最大的記錄，并將它參與到有序子序列中，以此方法添加記錄的有序子序列的長(zhǎng)度。3. 選擇類選擇類從記錄的無序子序列中“選擇關(guān)鍵字最小或最大的記錄，并將它參與到有序子

5、序列中，以此方法添加記錄的有序子序列的長(zhǎng)度。4. 歸并類歸并類經(jīng)過“歸并兩個(gè)或兩個(gè)以上的記錄有序子序列，逐漸添加記錄有序序列的長(zhǎng)度。5. 其它方法其它方法 10. 2 插插 入入 排排 序序有序序列R1.i-1Ri無序序列 Ri.n一趟直接插入排序的根本思想：有序序列R1.i無序序列 Ri+1.n實(shí)現(xiàn)實(shí)現(xiàn)“一趟插入排序可分三步進(jìn)展：一趟插入排序可分三步進(jìn)展：3將將Ri 插入插入(復(fù)制復(fù)制)到到Rj+1的位置的位置上。上。2將將Rj+1.i-1中的一切記錄均后移中的一切記錄均后移 一個(gè)位置；一個(gè)位置；1在在R1.i-1中查找中查找Ri的插入位置，的插入位置， R1.j.key Ri.key Rj

6、+1.i-1.key；直接插入排序基于順序直接插入排序基于順序查找查找表插入排序基于鏈表存儲(chǔ)表插入排序基于鏈表存儲(chǔ)不同的詳細(xì)實(shí)現(xiàn)方法導(dǎo)致不同的算法描畫不同的詳細(xì)實(shí)現(xiàn)方法導(dǎo)致不同的算法描畫折半插入排序基于折半折半插入排序基于折半查找查找希爾排序基于逐趟減少希爾排序基于逐趟減少增量增量一、直接插入排序一、直接插入排序利用 “順序查找實(shí)現(xiàn)“在R1.i-1中查找Ri的插入位置算法的實(shí)現(xiàn)要點(diǎn)：算法的實(shí)現(xiàn)要點(diǎn)：從Ri-1起向前進(jìn)展順序查找， 監(jiān)視哨設(shè)置在R0；R0 = Ri; / 設(shè)置“哨兵循環(huán)終了闡明Ri的插入位置為 j +1R0jRifor (j=i-1; R0.keyRj.key; -j); / 從

7、后往前找從后往前找j=i-1插入位置插入位置 對(duì)于在查找過程中找到的那些關(guān)鍵字不小于Ri.key的記錄，并在查找的同時(shí)實(shí)現(xiàn)記錄向后挪動(dòng)；for (j=i-1; R0.keyRj.key; -j); Rj+1 = RjR0jRij= i-1上述循環(huán)終了后可以直接進(jìn)展“插入插入位置插入位置令 i = 2，3，, n, 實(shí)現(xiàn)整個(gè)序列的排序。for ( i=2; i=n; +i ) if (Ri.keyRi-1.key) 在在 R1.i-1中查找中查找Ri的插入位置的插入位置; 插入插入Ri ; void InsertionSort ( SqList &L ) / 對(duì)順序表對(duì)順序表 L 作直接插入排序

8、。作直接插入排序。 for ( i=2; i=L.length; +i ) if (L.ri.key L.ri-1.key) / InsertSortL.r0 = L.ri; / 復(fù)制為監(jiān)視哨for ( j=i-1; L.r0.key L.rj.key; - j ) L.rj+1 = L.rj; / 記錄后移L.rj+1 = L.r0; / 插入到正確位置內(nèi)部排序的時(shí)間分析：實(shí)現(xiàn)內(nèi)部排序的根本操作有兩個(gè)：2“挪動(dòng)記錄。1“比較序列中兩個(gè)關(guān)鍵字的 大??；對(duì)于直接插入排序：最好的情況關(guān)鍵字在記錄序列中順序有序：最好的情況關(guān)鍵字在記錄序列中順序有序：“比較的次數(shù)：最壞的情況關(guān)鍵字在記錄序列中逆序有序

9、：最壞的情況關(guān)鍵字在記錄序列中逆序有序：“比較的次數(shù)：112nni02) 1)(4() 1(2nnini“挪動(dòng)的次數(shù)：“挪動(dòng)的次數(shù)：2) 1)(4() 1(2nnini 由于 R1.i-1 是一個(gè)按關(guān)鍵字有序的有序序列，那么可以利用折半查找實(shí)現(xiàn)“在R1.i-1中查找Ri的插入位置，如此實(shí)現(xiàn)的插入排序?yàn)檎郯氩迦肱判颉６?、折半插入排序二、折半插入排序void BiInsertionSort ( SqList &L ) / BInsertSort在在 L.r1.i-1中折半查找插入位置；中折半查找插入位置；for ( i=2; i=high+1; -j ) L.rj+1 = L.rj; / 記錄后移

10、記錄后移L.rhigh+1 = L.r0; / 插入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ū)插入點(diǎn)在低半?yún)^(qū)else low = m+1; / 插入點(diǎn)在高半?yún)^(qū)插入點(diǎn)在高半?yún)^(qū)14 36 49 52 80 58 61 23 97 75ilowhighmmlowlowmhigh14 36 49 52 58 61 80 23 97 75ilowhighmhighmhighmlow例如:再如:插入位置插入位置L.rL.r三、表插入排序三、表插

11、入排序 為了減少在排序過程中進(jìn)展的“挪動(dòng)記錄的操作，必需改動(dòng)排序過程中采用的存儲(chǔ)構(gòu)造。利用靜態(tài)鏈表進(jìn)展排序，并在排序完成之后，一次性地調(diào)整各個(gè)記錄相互之間的位置，即將每個(gè)記錄都調(diào)整到它們所應(yīng)該在的位置上。void LInsertionSort (Elem SL ， int n) / 對(duì)記錄序列對(duì)記錄序列SL1.n作表插入排序作表插入排序 SL0.key = MAXINT ; SL0.next = 1; SL1.next = 0; for ( i=2; i=n; +i ) for ( j=0, k = SL0.next;SLk.key= SLi.key ; j=k, k=SLk.next ) S

12、Lj.next = i; SLi.next = k; / 結(jié)點(diǎn)結(jié)點(diǎn)i插入在結(jié)點(diǎn)插入在結(jié)點(diǎn)j和結(jié)點(diǎn)和結(jié)點(diǎn)k之間之間/ LinsertionSort算法中運(yùn)用了三個(gè)指針：其中：p指示第i個(gè)記錄的當(dāng)前位置 i指示第i個(gè)記錄應(yīng)在的位置 q指示第i+1個(gè)記錄的當(dāng)前位置如何在排序之后調(diào)整記錄序列？如何在排序之后調(diào)整記錄序列？void Arrange ( Elem SL , int n ) p = SL0.next; / p指示第一個(gè)記錄的當(dāng)前位置指示第一個(gè)記錄的當(dāng)前位置 for ( i=1; in; +i ) while (pi) p = SLp.next; q = SLp.next; / q指示尚未調(diào)整

13、的表尾指示尚未調(diào)整的表尾 if ( p!= i ) SLpSLi; / 交換記錄，使第交換記錄，使第i個(gè)記錄到位個(gè)記錄到位 SLi.next = p; / 指向被移走的記錄指向被移走的記錄 p = q; / p指示尚未調(diào)整的表尾，指示尚未調(diào)整的表尾， / 為找第為找第i+1個(gè)記錄作預(yù)備個(gè)記錄作預(yù)備 / Arrange 四、希爾排序又稱減少增量排序四、希爾排序又稱減少增量排序 根本思想：對(duì)待排記錄序列先作“宏觀調(diào)整，再作“微觀調(diào)整。 所謂“宏觀調(diào)整，指的是，“騰躍式的插入排序。 詳細(xì)做法為：將記錄序列分成假設(shè)干子序列，分別對(duì)每個(gè)子序列進(jìn)展插入排序。其中，d 稱為增量，它的值在排序過程中從大到小逐

14、漸減少，直至最后一趟排序減為 1。例如：將 n 個(gè)記錄分成 d 個(gè)子序列： R1，R1+d，R1+2d，R1+kd R2，R2+d，R2+2d，R2+kd Rd，R2d，R3d，Rkd，R(k+1)d 例如：16 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 void ShellInsert (

15、 SqList &L, int dk ) for ( i=dk+1; i=n; +i ) if ( L.ri.key0&(L.r0.keyL.rj.key); j-=dk) L.rj+dk = L.rj; / 記錄后移，查找插入位置記錄后移，查找插入位置 L.rj+dk = L.r0; / 插入插入 / if / ShellInsertvoid ShellSort (SqList &L, int dlta, int t) / 增量為增量為dlta的希爾排序的希爾排序 for (k=0; k1) / while / BubbleSorti = n;i = lastExchangeIndex; /

16、 本趟進(jìn)展過交換的 / 最后一個(gè)記錄的位置 if (Rj+1.key Rj.key) Swap(Rj, Rj+1); lastExchangeIndex = j; /記下進(jìn)展交換的記錄位置 /iffor (j = 1; j i; j+)lastExchangeIndex = 1;留意留意: :2. 普通情況下，每經(jīng)過一趟“起泡，“i 減一，但并不是每趟都如此。例如例如:523197825531579 89i=7i=6for (j = 1; j i; j+) if (Rj+1.key Rj.key) 13i=21. 起泡排序的終了條件為， 最后一趟沒有進(jìn)展“交換記錄。時(shí)間分析時(shí)間分析: :最好的

17、情況關(guān)鍵字在記錄序列中順序有序：最好的情況關(guān)鍵字在記錄序列中順序有序： 只需進(jìn)展一趟起泡只需進(jìn)展一趟起泡“比較的次數(shù)：比較的次數(shù)：最壞的情況關(guān)鍵字在記錄序列中逆序有序：最壞的情況關(guān)鍵字在記錄序列中逆序有序： 需進(jìn)展需進(jìn)展n-1趟起泡趟起泡“比較的次數(shù)：比較的次數(shù)：0“挪動(dòng)的次數(shù)：挪動(dòng)的次數(shù)：“挪動(dòng)的次數(shù)：挪動(dòng)的次數(shù)：n-12) 1() 1(2nnini2) 1(3) 1(32nnini二、一趟快速排序一次劃分二、一趟快速排序一次劃分目的：找一個(gè)記錄，以它的關(guān)鍵字作為目的：找一個(gè)記錄，以它的關(guān)鍵字作為“樞軸，凡其關(guān)鍵字小于樞軸的記錄均樞軸，凡其關(guān)鍵字小于樞軸的記錄均挪動(dòng)至該記錄之前，反之，凡關(guān)鍵

18、字大于挪動(dòng)至該記錄之前，反之，凡關(guān)鍵字大于樞軸的記錄均挪動(dòng)至該記錄之后。樞軸的記錄均挪動(dòng)至該記錄之后。致使一趟排序之后，記錄的無序序列Rs.t將分割成兩部分：Rs.i-1和Ri+1.t，且 Rj.key Ri.key Rj.key (sji-1) 樞軸 (i+1jt)。52 49 80 36 14 58 61 97 23 75stlowhigh設(shè)設(shè) Rs=52 為樞軸為樞軸 將 Rhigh.key 和 樞軸的關(guān)鍵字進(jìn)展比較，要求Rhigh.key 樞軸的關(guān)鍵字 將 Rlow.key 和 樞軸的關(guān)鍵字進(jìn)展比較，要求Rlow.key 樞軸的關(guān)鍵字high23low80high14low52例如例如

19、R052lowhighhighhighlow 可見，經(jīng)過“一次劃分 ，將關(guān)鍵字序列 52, 49, 80, 36, 14, 58, 61, 97, 23, 75 調(diào)整為: 23, 49, 14, 36, (52) 58, 61, 97, 80, 75 在調(diào)整過程中，設(shè)立了兩個(gè)指針： low 和high，它們的初值分別為： s 和 t， 之后逐漸減小 high，添加 low，并保證 Rhigh.key52，和 Rlow.key52,否那么進(jìn)展記錄的“交換。int Partition (RedType& R, int low, int high) pivotkey = Rlow.key; whil

20、e (lowhigh) while (low=pivotkey) -high; RlowRhigh; while (lowhigh & Rlow.key=pivotkey) +low; RlowRhigh; return low; / 前往樞軸所在位置前往樞軸所在位置 / Partitionint Partition (RedType R, int low, int high) / Partition R0 = Rlow; pivotkey = Rlow.key; / 樞軸 while (lowhigh) while(low=pivotkey) - high; / 從右向左搜索從右向左搜索Rl

21、ow = Rhigh;while (lowhigh & Rlow.key=pivotkey) + low; / 從左向右搜索從左向右搜索Rhigh = Rlow;Rlow = R0; return low;三、快速排序三、快速排序 首先對(duì)無序的記錄序列進(jìn)展“一次劃分，之后分別對(duì)分割所得兩個(gè)子序列“遞歸進(jìn)展快速排序。無 序 的 記 錄 序 列無序記錄子序列(1)無序子序列(2)樞軸樞軸一次劃分分別進(jìn)展快速排序void QSort (RedType & R, int s, int t ) / 對(duì)記錄序列對(duì)記錄序列Rs.t進(jìn)展快速排序進(jìn)展快速排序 if (s t-1) / 長(zhǎng)度大于長(zhǎng)度大于1 / Q

22、Sortpivotloc = Partition(R, s, t); / 對(duì) Rs.t 進(jìn)展一次劃分QSort(R, s, pivotloc-1); / 對(duì)低子序列遞歸排序，pivotloc是樞軸位置QSort(R, pivotloc+1, t); / 對(duì)高子序列遞歸排序void QuickSort( SqList & L) / 對(duì)順序表進(jìn)展快速排序?qū)樞虮磉M(jìn)展快速排序 QSort(L.r, 1, L.length); / QuickSort 第一次調(diào)用函數(shù) Qsort 時(shí)，待排序記錄序列的上、下界分別為 1 和 L.length。四、快速排序的時(shí)間分析四、快速排序的時(shí)間分析假設(shè)一次劃分所得樞

23、軸位置 i=k，那么對(duì)n 個(gè)記錄進(jìn)展快排所需時(shí)間：其中 Tpass(n)為對(duì) n 個(gè)記錄進(jìn)展一次劃分所需時(shí)間。 假設(shè)待排序列中記錄的關(guān)鍵字是隨機(jī)分布的，那么 k 取 1 至 n 中恣意一值的能夠性一樣。T(n) = Tpass(n) + T(k-1) + T(n-k)nkavgavgavgknTkTnCnnT1)() 1(1)(設(shè) Tavg(1)b那么可得結(jié)果：) 1ln() 1)(22()(nncbnTavg結(jié)論結(jié)論: 快速排序的時(shí)間復(fù)雜度為快速排序的時(shí)間復(fù)雜度為O(nlogn)由此可得快速排序所需時(shí)間的平均值為： 假設(shè)待排記錄的初始形狀為按關(guān)鍵字有假設(shè)待排記錄的初始形狀為按關(guān)鍵字有序時(shí)，快

24、速排序?qū)⑼懟癁槠鹋菖判?，其時(shí)序時(shí)，快速排序?qū)⑼懟癁槠鹋菖判?，其時(shí)間復(fù)雜度為間復(fù)雜度為O(n2)。 為防止出現(xiàn)這種情況，需在進(jìn)展一次劃分之前，進(jìn)展“予處置，即： 先對(duì) R(s).key, R(t).key 和 R(s+t)/2.key，進(jìn)展相互比較，然后取關(guān)鍵字為 “三者之中的記錄為樞軸記錄。10.4 堆堆 排排 序序簡(jiǎn)簡(jiǎn) 單單 選選 擇擇 排排 序序堆堆 排排 序序一、簡(jiǎn)單項(xiàng)選擇擇排序一、簡(jiǎn)單項(xiàng)選擇擇排序假設(shè)排序過程中，待排記錄序列的形狀為：有序序列R1.i-1無序序列 Ri.n 第 i 趟簡(jiǎn)單項(xiàng)選擇擇排序從中選出關(guān)鍵字最小的記錄有序序列R1.i無序序列 Ri+1.n簡(jiǎn)單項(xiàng)選擇擇排序的算法描畫

25、如下：void SelectSort (Elem R, int n ) / 對(duì)記錄序列對(duì)記錄序列R1.n作簡(jiǎn)單項(xiàng)選擇擇排序。作簡(jiǎn)單項(xiàng)選擇擇排序。 for (i=1; i0; -i ) HeapAdjust ( H.r, i, H.length ); / 建大頂堆建大頂堆for ( i=H.length; i1; -i ) H.r1H.ri; / 將堆頂記錄和當(dāng)前未經(jīng)排序子序列將堆頂記錄和當(dāng)前未經(jīng)排序子序列 / H.r1.i中最后一個(gè)記錄相互交換中最后一個(gè)記錄相互交換 HeapAdjust(H.r, 1, i-1); / 對(duì)對(duì) H.r1 進(jìn)展挑選進(jìn)展挑選如何如何“建堆？建堆？?jī)蓚€(gè)問題兩個(gè)問題:如

26、何如何“挑選？挑選？定義堆類型為定義堆類型為:typedef SqList HeapType; / 堆采用順序表表示之堆采用順序表表示之所謂“挑選指的是，對(duì)一棵左/右子樹均為堆的完全二叉樹，“調(diào)整根結(jié)點(diǎn)使整個(gè)二叉樹也成為一個(gè)堆。堆堆挑選挑選98814973556412362740例如例如:是大頂堆是大頂堆12但在 98 和 12 進(jìn)展互換之后，它就不是堆了，因此，需求對(duì)它進(jìn)展“挑選。98128173641298比較比較比較void HeapAdjust (RcdType &R, int s, int m) / 知知 Rs.m中記錄的關(guān)鍵字除中記錄的關(guān)鍵字除 Rs 之外之外均均 / 滿足堆的特征

27、，本函數(shù)自上而下調(diào)整滿足堆的特征，本函數(shù)自上而下調(diào)整 Rs 的的 / 關(guān)鍵字，使關(guān)鍵字，使 Rs.m 也成為一個(gè)大頂堆也成為一個(gè)大頂堆 / HeapAdjustrc = Rs; / 暫存 Rs for ( j=2*s; j= Rj.key ) break; / 再作再作“根和根和“子樹根之間的比子樹根之間的比較，較， / 假設(shè)假設(shè)“=成立，那么闡明已找成立，那么闡明已找到到 rc 的插的插 / 入位置入位置 s ，不需求繼續(xù)往下調(diào)整，不需求繼續(xù)往下調(diào)整Rs = Rj; s = j; / 否那么記錄上移，尚需繼續(xù)往下調(diào)整否那么記錄上移，尚需繼續(xù)往下調(diào)整if ( jm & Rj.keyRj+1.k

28、ey ) +j; / 左左/右右“子樹根之間先進(jìn)展相互子樹根之間先進(jìn)展相互比較比較 / 令令 j 指示關(guān)鍵字較大記錄的位置指示關(guān)鍵字較大記錄的位置建堆是一個(gè)從下往上進(jìn)展建堆是一個(gè)從下往上進(jìn)展“挑選的過程。挑選的過程。40554973816436122798例如例如: 排序之前的關(guān)鍵字序列為排序之前的關(guān)鍵字序列為123681734998817355 如今，左/右子樹都曾經(jīng)調(diào)整為堆，最后只需調(diào)整根結(jié)點(diǎn)，使整個(gè)二叉樹是個(gè)“堆即可。98494064361227堆排序的時(shí)間復(fù)雜度分析：堆排序的時(shí)間復(fù)雜度分析：1. 對(duì)深度為對(duì)深度為 k 的堆，的堆，“挑選所需進(jìn)展的關(guān)鍵字挑選所需進(jìn)展的關(guān)鍵字比較的次數(shù)至多

29、為比較的次數(shù)至多為2(k-1)；3. 調(diào)整調(diào)整“堆頂堆頂 n-1 次，總共進(jìn)展的關(guān)鍵次，總共進(jìn)展的關(guān)鍵 字比較的次數(shù)不超越字比較的次數(shù)不超越 2 (log2(n-1) + log2(n-2) + +log22) 2n(log2n ) 因此，堆排序的時(shí)間復(fù)雜度為O(nlogn)。2. 對(duì)對(duì) n 個(gè)關(guān)鍵字，建成深度為個(gè)關(guān)鍵字，建成深度為h(=log2n +1)的堆，的堆，所需進(jìn)展的關(guān)鍵字比較的次數(shù)至多所需進(jìn)展的關(guān)鍵字比較的次數(shù)至多 4n；10.5 歸歸 并并 排排 序序歸并排序的過程基于以下根本思想進(jìn)展： 將兩個(gè)或兩個(gè)以上的有序子序列 “歸并 為一個(gè)有序序列。在內(nèi)部排序中，通常采用的是2-路歸并排

30、序。即：將兩個(gè)位置相鄰的記錄有序子序列歸并為一個(gè)記錄的有序序列。有有 序序 序序 列列 Rl.n有序子序列有序子序列 Rl.m 有序子序列有序子序列 Rm+1.n這個(gè)操作對(duì)順序表而言，是輕而易舉的。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.ke

31、y=SRj.key) TRk = SRi+; else TRk = SRj+; if (i=m) TRk.n = SRi.m; / 將剩余的將剩余的 SRi.m 復(fù)制到復(fù)制到 TRif (j=n) TRk.n = SRj.n; / 將剩余的將剩余的 SRj.n 復(fù)制到復(fù)制到 TR歸并排序的算法歸并排序的算法假設(shè)記錄無序序列 Rs.t 的兩部分 Rs.(s+t)/2 和 R(s+t)/2+1.t分別按關(guān)鍵字有序，那么利用上述歸并算法很容易將它們歸并成整個(gè)記錄序列是一個(gè)有序序列。 由此，應(yīng)該先分別對(duì)這兩部分進(jìn)展 2-路歸并排序。例如：例如：52, 23, 80, 36, 68, 14 (s=1,

32、t=6) 52, 23, 80 36, 68, 14 52, 2380 52 23, 52 23, 52, 8036, 6814366836, 6814, 36, 68 14, 23, 36, 52, 68, 80 23void Msort ( RcdType SR, RcdType &TR1, int s, int t ) / 將將SRs.t 歸并排序?yàn)闅w并排序?yàn)?TR1s.t if (s= =t) TR1s=SRs; else / Msort m = (s+t)/2; / 將SRs.t平分為SRs.m和SRm+1.tMsort (SR, TR2, s, m); / 遞歸地將SRs.m歸并為

33、有序的TR2s.mMsort (SR, TR2, m+1, t); /遞歸地SRm+1.t歸并為有序的TR2m+1.tMerge (TR2, TR1, s, m, t); / 將TR2s.m和TR2m+1.t歸并到TR1s.tvoid MergeSort (SqList &L) / 對(duì)順序表對(duì)順序表 L 作作2-路歸并排序路歸并排序 MSort(L.r, L.r, 1, L.length); / MergeSort容易看出，對(duì) n 個(gè)記錄進(jìn)展歸并排序的時(shí)間復(fù)雜度為(nlogn)。即： 每一趟歸并的時(shí)間復(fù)雜度為 O(n)， 總共需進(jìn)展 log2n 趟。10.6 基基 數(shù)數(shù) 排排 序序基數(shù)排序是一

34、種借助“多關(guān)鍵字排序的思想來實(shí)現(xiàn)“單關(guān)鍵字排序的內(nèi)部排序算法。多關(guān)鍵字的排序多關(guān)鍵字的排序鏈?zhǔn)交鶖?shù)排序鏈?zhǔn)交鶖?shù)排序一、多關(guān)鍵字的排序一、多關(guān)鍵字的排序 n 個(gè)記錄的序列個(gè)記錄的序列 R1, R2, ，Rn對(duì)關(guān)鍵字對(duì)關(guān)鍵字 (Ki0, Ki1,Kid-1) 有序是有序是指：指： 其中其中: K0 : K0 被稱為被稱為 “ “最主位關(guān)鍵字最主位關(guān)鍵字Kd-1 被稱為被稱為 “最次位關(guān)鍵字最次位關(guān)鍵字 對(duì)于序列中恣意兩個(gè)記錄 Ri 和 Rj(1ijn) 都滿足以下(詞典)有序關(guān)系： (Ki0, Ki1, ,Kid-1) (Kj0, Kj1, ,Kjd-1) 實(shí)現(xiàn)多關(guān)鍵字排序通常有兩種作法:最低位優(yōu)

35、先最低位優(yōu)先LSDLSD法法最高位優(yōu)先最高位優(yōu)先MSDMSD法法先對(duì)先對(duì)K0K0進(jìn)展排序，并按進(jìn)展排序，并按 K0 K0 的不的不同值將記錄序列分成假設(shè)干子序同值將記錄序列分成假設(shè)干子序列之后，分別對(duì)列之后，分別對(duì) K1 K1 進(jìn)展排進(jìn)展排序，序，.， 依次類推，直至最依次類推，直至最后對(duì)最次位關(guān)鍵字排序完成為止。后對(duì)最次位關(guān)鍵字排序完成為止。 先對(duì) Kd-1 進(jìn)展排序，然后對(duì) Kd-2 進(jìn)展排序，依次類推，直至對(duì)最主位關(guān)鍵字 K0 排序完成為止。 排序過程中不需求根據(jù) “前一個(gè) 關(guān)鍵字的排序結(jié)果，將記錄序列分割成假設(shè)干個(gè)(“前一個(gè)關(guān)鍵字不同的)子序列。例如例如: :學(xué)生記錄含三個(gè)關(guān)鍵字學(xué)生記

36、錄含三個(gè)關(guān)鍵字: :系別、班號(hào)和班內(nèi)的序列號(hào)，其中以系別、班號(hào)和班內(nèi)的序列號(hào)，其中以系別為最主位關(guān)鍵字。系別為最主位關(guān)鍵字。 無序序列對(duì)對(duì)K2排序排序?qū)?duì)K1排序排序?qū)?duì)K0排序排序3,2,301,2,153,1,202,3,182,1,201,2,152,3,183,1,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的排序過程如下的排序過程如下:二、鏈?zhǔn)交鶖?shù)排序二、鏈?zhǔn)交鶖?shù)排序假設(shè)多關(guān)鍵字的記錄序列中，每個(gè)關(guān)鍵字的取值范圍一樣，那么按LSD法進(jìn)展排序時(shí)，可以采用“分配-搜集的方法，其

37、益處是不需求進(jìn)展關(guān)鍵字間的比較。對(duì)于數(shù)字型或字符型的單關(guān)鍵字，可以看成是由多個(gè)數(shù)位或多個(gè)字符構(gòu)成的多關(guān)鍵字，此時(shí)可以采用這種“分配-搜集的方法進(jìn)展排序，稱作基數(shù)排序法。例如：對(duì)以下這組關(guān)鍵字例如：對(duì)以下這組關(guān)鍵字 209, 386, 768, 185, 247, 606, 230, 834, 539 首先按其 “個(gè)位數(shù) 取值分別為 0, 1, , 9 “分配 成 10 組，之后按從 0 至 9 的順序?qū)?它們 “搜集 在一同； 然后按其 “十位數(shù) 取值分別為 0, 1, , 9 “分配 成 10 組，之后再按從 0 至 9 的順序?qū)⑺鼈?“搜集 在一同；最后按其“百位數(shù)反復(fù)一遍上述操作。在計(jì)算

38、機(jī)上實(shí)現(xiàn)基數(shù)排序時(shí)，為減少所需輔助存儲(chǔ)空間，應(yīng)采用鏈表作存儲(chǔ)構(gòu)造，即鏈?zhǔn)交鶖?shù)排序，詳細(xì)作法為： 待排序記錄以指針相鏈，構(gòu)成一個(gè)鏈表；“分配分配 時(shí)，按當(dāng)前時(shí)，按當(dāng)前“關(guān)鍵字位關(guān)鍵字位所取值，將記錄分配到不同的所取值，將記錄分配到不同的 “鏈隊(duì)列鏈隊(duì)列 中，每個(gè)隊(duì)列中記錄的中，每個(gè)隊(duì)列中記錄的 “關(guān)鍵字位關(guān)鍵字位 一樣；一樣；“搜集時(shí)，按當(dāng)前關(guān)鍵字位取值從搜集時(shí)，按當(dāng)前關(guān)鍵字位取值從小到大將各隊(duì)列首尾相鏈成一個(gè)鏈表小到大將各隊(duì)列首尾相鏈成一個(gè)鏈表; ;對(duì)每個(gè)關(guān)鍵字位均反復(fù)對(duì)每個(gè)關(guān)鍵字位均反復(fù) 2) 2) 和和 3) 3) 兩步。兩步。例如：p369367167239237230進(jìn)展第一次分配進(jìn)展

39、第一次分配進(jìn)展第一次搜集進(jìn)展第一次搜集f0 r0f7 r7f8 r8f9 r9p230230367 167237367167237368239369 239進(jìn)展第二次分配進(jìn)展第二次分配p230237239p230367167237368239f3 r3f6 r6230 237239367 167368367167368進(jìn)展第二次搜集 進(jìn)展第三次搜集之后便得到記錄的有序序列f1 r1p230237239367167368進(jìn)展第三次分配進(jìn)展第三次分配f2 r2f3 r3 167230 237239367 368p167230237239367368提示留意：提示留意：“分配和分配和“搜集的實(shí)踐操作

40、搜集的實(shí)踐操作僅為修正鏈表中的指針和設(shè)置隊(duì)列的僅為修正鏈表中的指針和設(shè)置隊(duì)列的頭、尾指針；頭、尾指針；為查找運(yùn)用，該鏈表尚需運(yùn)用算為查找運(yùn)用，該鏈表尚需運(yùn)用算法法Arrange 將它調(diào)整為有序表。將它調(diào)整為有序表。 基數(shù)排序的時(shí)間復(fù)雜度為O(d(n+rd)其中：分配為O(n) 搜集為O(rd)(rd為“基) d為“分配-搜集的趟數(shù)10.7 各種排序方法的綜合比較各種排序方法的綜合比較一、時(shí)間性能一、時(shí)間性能1. 平均的時(shí)間性能平均的時(shí)間性能基數(shù)排序基數(shù)排序時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為 O(nlogn)：快速排序、堆排序和歸并排序快速排序、堆排序和歸并排序時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為 O(n2) O(n

41、2)：直接插入排序、起泡排序和直接插入排序、起泡排序和簡(jiǎn)單項(xiàng)選擇擇排序簡(jiǎn)單項(xiàng)選擇擇排序時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為 O(n):2. 當(dāng)待排記錄序列按關(guān)鍵字順序有序時(shí)當(dāng)待排記錄序列按關(guān)鍵字順序有序時(shí)3. 簡(jiǎn)單項(xiàng)選擇擇排序、堆排序和歸并排簡(jiǎn)單項(xiàng)選擇擇排序、堆排序和歸并排序的時(shí)間性能不隨記錄序列中關(guān)鍵字的序的時(shí)間性能不隨記錄序列中關(guān)鍵字的分布而改動(dòng)。分布而改動(dòng)。 直接插入排序和起泡排序能到達(dá)O(n)的時(shí)間復(fù)雜度， 快速排序的時(shí)間性能蛻化為O(n2) 。二、空間性能二、空間性能指的是排序過程中所需的輔助空間大小1. 一切的簡(jiǎn)單排序方法一切的簡(jiǎn)單排序方法(包括：直接插包括：直接插入、入、起泡和簡(jiǎn)單項(xiàng)選擇擇起

42、泡和簡(jiǎn)單項(xiàng)選擇擇) 和堆排序的空和堆排序的空間復(fù)雜度為間復(fù)雜度為O(1)；2. 快速排序?yàn)榭焖倥判驗(yàn)镺(logn)，為遞歸程序執(zhí)，為遞歸程序執(zhí)行過程中，棧所需的輔助空間；行過程中，棧所需的輔助空間；3. 歸并排序所需輔助空間最多，其歸并排序所需輔助空間最多，其空間復(fù)雜度為空間復(fù)雜度為 O(n);4. 鏈?zhǔn)交鶖?shù)排序需附設(shè)隊(duì)列首尾指鏈?zhǔn)交鶖?shù)排序需附設(shè)隊(duì)列首尾指針，那么空間復(fù)雜度為針，那么空間復(fù)雜度為 O(rd)。三、排序方法的穩(wěn)定性能三、排序方法的穩(wěn)定性能 1. 穩(wěn)定的排序方法指的是，對(duì)于兩個(gè)關(guān)鍵字相等的記錄，它們?cè)谛蛄兄械南鄬?duì)位置，在排序之前和經(jīng)過排序之后，沒有改動(dòng)。 2. 當(dāng)對(duì)多關(guān)鍵字的記錄序

43、列進(jìn)展當(dāng)對(duì)多關(guān)鍵字的記錄序列進(jìn)展LSD方法排序時(shí)，必需采用穩(wěn)定的排序方方法排序時(shí)，必需采用穩(wěn)定的排序方法。法。排序之前 : Ri(K) Rj(K) 排序之后 : Ri(K) Rj(K) 例如：例如： 排序前 ( 56, 34, 47, 23, 66, 18, 82, 47 )假設(shè)排序后得到結(jié)果 ( 18, 23, 34, 47, 47, 56, 66, 82 )那么稱該排序方法是穩(wěn)定的;假設(shè)排序后得到結(jié)果 ( 18, 23, 34, 47, 47, 56, 66, 82 )那么稱該排序方法是不穩(wěn)定的。 3. 對(duì)于不穩(wěn)定的排序方法，只需能對(duì)于不穩(wěn)定的排序方法，只需能舉出一個(gè)實(shí)例闡明即可。舉出一個(gè)

44、實(shí)例闡明即可。 4. 快速排序、堆排序和希爾排序是不穩(wěn)快速排序、堆排序和希爾排序是不穩(wěn)定的排序方法。定的排序方法。例如例如 : 對(duì)對(duì) 4, 3, 4, 2 進(jìn)展快速排序，進(jìn)展快速排序， 得到得到 2, 3, 4, 4 四、關(guān)于四、關(guān)于“排序方法的時(shí)間復(fù)雜度的下限排序方法的時(shí)間復(fù)雜度的下限 本章討論的各種排序方法，除基數(shù)排序外，其它方法都是基于“比較關(guān)鍵字進(jìn)展排序的排序方法。 可以證明， 這類排序法能夠到達(dá)的最快的時(shí)間復(fù)雜度為O(nlogn)。 (基數(shù)排序不是基于“比較關(guān)鍵字的排序方法，所以它不受這個(gè)限制。) 例如:對(duì)三個(gè)關(guān)鍵字進(jìn)展排序的斷定樹如下：K1K3K1K2K1K3K2K3K2 K3K2

45、K1K3K1K2K3K3K2K1K2K3K1K3K1K2 K1K3K2樹上的每一次“比較都是必要的;樹上的葉子結(jié)點(diǎn)包含一切能夠情況。 普通情況下，對(duì)n個(gè)關(guān)鍵字進(jìn)展排序，能夠得到的結(jié)果有n! 種，由于含n! 個(gè)葉子結(jié)點(diǎn)的二叉樹的深度不小于log2(n!) +1, 那么對(duì) n 個(gè)關(guān)鍵字進(jìn)展排序的比較次數(shù)至少是 log2(n!) nlog2n (斯蒂林近似公式)。 所以，基于“比較關(guān)鍵字進(jìn)展排序的排序方法，能夠到達(dá)的最快的時(shí)間復(fù)雜度為 O(nlogn)。10.8外外 部部 排排 序序一一. 問題的提出問題的提出 待排序的記錄數(shù)量很大，不能待排序的記錄數(shù)量很大，不能一次裝入內(nèi)存，那么無法利用前幾一次裝入內(nèi)存，那么無法利用前幾節(jié)節(jié)討論的排序方法討論的排序方法 (否那么將引起頻繁否那么將引起頻繁訪問內(nèi)存訪問內(nèi)存)； 對(duì)外存中數(shù)據(jù)的讀對(duì)外存中數(shù)據(jù)的讀/寫是以寫是以“數(shù)據(jù)數(shù)據(jù)塊塊為單位進(jìn)展的；為單位進(jìn)展的； 讀讀/寫外存中一個(gè)寫外存中一個(gè)“數(shù)據(jù)塊的數(shù)據(jù)所數(shù)據(jù)塊的數(shù)據(jù)所需求的時(shí)間為：需求的時(shí)間為： TI/O = tseek + tla + n twm 其中其中 tseek 為尋查時(shí)間為尋查時(shí)間(查找該數(shù)據(jù)塊所查找該數(shù)據(jù)塊所在磁道在磁道) tla 為等待為等待(延遲延遲)時(shí)間時(shí)間 n twm 為傳輸數(shù)據(jù)