1、會(huì)計(jì)學(xué)1數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(sh j ji u)分析分析第一頁，共105頁。10.1 概述概述(i sh)10.2 插入排序插入排序10.3 快速快速(kui s)排序排序10.4 堆排序堆排序10.5 歸并歸并(gubng)排序排序10.6 基數(shù)排序基數(shù)排序10.7 各種排序方法的綜合比較各種排序方法的綜合比較10.8 外部排序外部排序第1頁/共105頁第二頁，共105頁。10.1 概概 述述一、排序一、排序(pi x)的定義的定義二、內(nèi)部排序二、內(nèi)部排序(pi x)和外部排序和外部排序(pi x)三、內(nèi)部三、內(nèi)部(nib)排序方法的分類排序方法的分類第2頁/共105頁第三頁，共105頁。一、

2、什么一、什么(shn me)是排序？是排序？排序是計(jì)算機(jī)內(nèi)經(jīng)常(jngchng)進(jìn)行的一種操作，其目的是將一組“無序”的記錄序列調(diào)整為“有序”的記錄序列。例如：將下列(xili)關(guān)鍵字序列52, 49, 80, 36, 14, 58, 61, 23, 97, 75調(diào)整為14, 23, 36, 49, 52, 58, 61 ,75, 80, 97第3頁/共105頁第四頁，共105頁。 一般情況(qngkung)下，假設(shè)含n個(gè)記錄的序列為 R1, R2, ， Rn 其相應(yīng)的關(guān)鍵字序列為 K1, K2, ，Kn 這些關(guān)鍵字相互之間可以(ky)進(jìn)行比較，即在它們之間存在著這樣一個(gè)關(guān)系 ： Kp1Kp2

3、Kpn按此固有關(guān)系將上式記錄序列重新排列為 Rp1, Rp2, ，Rpn 的操作(cozu)稱作排序。第4頁/共105頁第五頁，共105頁。二、內(nèi)部排序二、內(nèi)部排序(pi x)和外部排序和外部排序(pi x)若整個(gè)(zhngg)排序過程不需要訪問外存便能完成，則稱此類排序問題為內(nèi)部排序； 反之，若參加排序的記錄數(shù)量很大， 整個(gè)序列的排序過程不可能在內(nèi)存中 完成，則稱此類排序問題(wnt)為外部排序。第5頁/共105頁第六頁，共105頁。三、內(nèi)部排序三、內(nèi)部排序(pi x)的方法的方法內(nèi)部排序的過程是一個(gè)逐步擴(kuò)大(kud)記錄的有序序列長度的過程。經(jīng)過經(jīng)過(jnggu)一一趟排序趟排序有序序列區(qū)

4、無 序 序 列 區(qū)有序序列區(qū)無 序 序 列 區(qū)第6頁/共105頁第七頁，共105頁?；诓煌摹皵U(kuò)大” 有序序列長度的方法，內(nèi)部排序(pi x)方法大致可分下列幾種類型：插入插入(ch r)類類交換交換(jiohun)類類選擇類選擇類 歸并類歸并類其它方法其它方法第7頁/共105頁第八頁，共105頁。待排記錄的數(shù)據(jù)類型定義待排記錄的數(shù)據(jù)類型定義(dngy)如下如下:#define MAXSIZE 1000 / 待排順序待排順序(shnx)表最大長度表最大長度typedef int KeyType; / 關(guān)鍵字類型關(guān)鍵字類型(lixng)為整數(shù)類型為整數(shù)類型(lixng)typedef stru

5、ct KeyType key; / 關(guān)鍵字項(xiàng)關(guān)鍵字項(xiàng) InfoType otherinfo; / 其它數(shù)據(jù)項(xiàng)其它數(shù)據(jù)項(xiàng) RcdType; / 記錄類型記錄類型typedef struct RcdType rMAXSIZE+1; / r0閑置閑置 int length; / 順序表長度順序表長度 SqList; / 順序表類型順序表類型第8頁/共105頁第九頁，共105頁。1. 插入插入(ch r)類類將無序子序列中的一個(gè)或幾個(gè)記錄“插入”到有序序列中，從而(cng r)增加記錄的有序子序列的長度。第9頁/共105頁第十頁，共105頁。2. 交換交換(jiohun)類類通過“交換”無序序列中的記

6、錄從而得到其中關(guān)鍵字最小或最大的記錄，并將它加入(jir)到有序子序列中，以此方法增加記錄的有序子序列的長度。第10頁/共105頁第十一頁，共105頁。3. 選擇選擇(xunz)類類從記錄的無序(w x)子序列中“選擇”關(guān)鍵字最小或最大的記錄，并將它加入到有序子序列中，以此方法增加記錄的有序子序列的長度。第11頁/共105頁第十二頁，共105頁。4. 歸并歸并(gubng)類類通過“歸并”兩個(gè)(lin )或兩個(gè)(lin )以上的記錄有序子序列，逐步增加記錄有序序列的長度。5. 其它其它(qt)方法方法第12頁/共105頁第十三頁，共105頁。 10. 2 插插 入入 排排 序序第13頁/共10

7、5頁第十四頁，共105頁。有序序列(xli)R1.i-1Ri無序(w x)序列 Ri.n一趟直接(zhji)插入排序的基本思想：有序序列R1.i無序序列 Ri+1.n第14頁/共105頁第十五頁，共105頁。實(shí)現(xiàn)實(shí)現(xiàn)(shxin)“一趟插入排序一趟插入排序”可分三步進(jìn)行：可分三步進(jìn)行：3將將Ri 插入插入(ch r)(復(fù)制復(fù)制)到到Rj+1的的位置上。位置上。2將將Rj+1.i-1中的所有記錄均后移中的所有記錄均后移 一個(gè)一個(gè)(y )位置；位置；1在R1.i-1中查找查找Ri的插入位置， R1.j.key Ri.key Rj+1.i-1.key；第15頁/共105頁第十六頁，共105頁。直接插

8、入排序（基于順序直接插入排序（基于順序(shnx)查找）查找）表插入排序（基于表插入排序（基于(jy)鏈表存儲(chǔ)）鏈表存儲(chǔ)）不同不同(b tn)的具體實(shí)現(xiàn)方法導(dǎo)致不同的具體實(shí)現(xiàn)方法導(dǎo)致不同(b tn)的算法描述的算法描述折半插入排序折半插入排序（基于折半查找）（基于折半查找）希爾排序希爾排序（基于逐趟縮小增量）（基于逐趟縮小增量）第16頁/共105頁第十七頁，共105頁。一、直接一、直接(zhji)插插入排序入排序利用(lyng) “順序查找”實(shí)現(xiàn)“在R1.i-1中查找Ri的插入位置”算法的實(shí)現(xiàn)算法的實(shí)現(xiàn)(shxin)要點(diǎn)：要點(diǎn)：第17頁/共105頁第十八頁，共105頁。從Ri-1起向前(xin

9、 qin)進(jìn)行順序查找， 監(jiān)視哨設(shè)置在R0；R0 = Ri; / 設(shè)置(shzh)“哨兵”循環(huán)結(jié)束表明Ri的插入(ch r)位置為 j +1R0jRifor (j=i-1; R0.keyRj.key; -j); / 從后往前找j=i-1插入位置插入位置第18頁/共105頁第十九頁，共105頁。 對于在查找過程中找到的那些關(guān)鍵字不小于Ri.key的記錄，并在查找的同時(shí)(tngsh)實(shí)現(xiàn)記錄向后移動(dòng)；for (j=i-1; R0.keyRj.key; -j); Rj+1 = RjR0jRij= i-1上述循環(huán)結(jié)束后可以直接(zhji)進(jìn)行“插入”插入插入(ch r)位置位置第19頁/共105頁第二

10、十頁，共105頁。令 i = 2，3，, n, 實(shí)現(xiàn)整個(gè)序列(xli)的排序。for ( i=2; i=n; +i ) if (Ri.keyRi-1.key) 在在 R1.i-1中查找中查找Ri的插入的插入(ch r)位置位置; 插入插入(ch r)Ri ; 第20頁/共105頁第二十一頁，共105頁。void InsertionSort ( SqList &L ) / 對順序?qū)樞?shnx)表表 L 作直接插入排序。作直接插入排序。 for ( i=2; i=L.length; +i ) if (L.ri.key L.ri-1.key) / InsertSortL.r0 = L.r

11、i; / 復(fù)制為監(jiān)視哨for ( j=i-1; L.r0.key L.rj.key; - j ) L.rj+1 = L.rj; / 記錄后移L.rj+1 = L.r0; / 插入到正確(zhngqu)位置第21頁/共105頁第二十二頁，共105頁。內(nèi)部(nib)排序的時(shí)間分析：實(shí)現(xiàn)內(nèi)部排序(pi x)的基本操作有兩個(gè)：（2）“移動(dòng)(ydng)”記錄。（1）“比較比較”序列中兩個(gè)關(guān)鍵字的 大?。坏?2頁/共105頁第二十三頁，共105頁。對于(duy)直接插入排序：最好的情況（關(guān)鍵字在記錄序列最好的情況（關(guān)鍵字在記錄序列(xli)中順序有序）：中順序有序）：“比較(bjio)”的次數(shù)：最壞的情況

12、（關(guān)鍵字在記錄序列中逆序有序）：最壞的情況（關(guān)鍵字在記錄序列中逆序有序）：“比較”的次數(shù)：112nni02) 1)(4() 1(2nnini“移動(dòng)”的次數(shù)：“移動(dòng)”的次數(shù)：2) 1)(4() 1(2nnini第23頁/共105頁第二十四頁，共105頁。 二、希爾排序二、希爾排序(pi x)（又稱縮小增量排序（又稱縮小增量排序(pi x)） 基本(jbn)思想：對待排記錄序列先作“宏觀”調(diào)整，再作“微觀”調(diào)整。 所謂“宏觀(hnggun)”調(diào)整，指的是，“跳躍式”的插入排序。 具體做法為：第24頁/共105頁第二十五頁，共105頁。將記錄序列(xli)分成若干子序列(xli)，分別對每個(gè)子序列(

13、xli)進(jìn)行插入排序。其中，d 稱為增量，它的值在排序過程中從大到小逐漸縮小(suxio)，直至最后一趟排序減為 1。例如(lr)：將 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 第25頁/共105頁第二十六頁，共105頁。例如(lr)：16 25 12 30 47 11 23 36 9 18 31 第一趟希爾排序(pi x)，設(shè)增量 d =511 23 12 9 18 16 25 36 30 47 31 第二趟希爾排序(pi x)，設(shè)增量 d = 39 18 12 11 23 1

14、6 25 31 30 47 36第三趟希爾排序，設(shè)增量 d = 1 9 11 12 16 18 23 25 30 31 36 47 第26頁/共105頁第二十七頁，共105頁。void ShellInsert ( 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; / 記錄后移，查找記錄后移，查找(ch zho)插入位置插入位置 L.rj+dk = L.r0; / 插入插入 / if / ShellInsert第27頁/共105

15、頁第二十八頁，共105頁。void ShellSort (SqList &L, int dlta, int t) / 增量增量(zn lin)為為dlta的希爾排序的希爾排序 for (k=0; k1) / while / BubbleSorti = n;i = lastExchangeIndex; / 本趟進(jìn)行過交換的 / 最后一個(gè)記錄(jl)的位置 if (Rj+1.key Rj.key) Swap(Rj, Rj+1); lastExchangeIndex = j; /記下(j xi)進(jìn)行交換的記錄位置 /iffor (j = 1; j i; j+)lastExchangeInde

16、x = 1;第31頁/共105頁第三十二頁，共105頁。注意注意(zh (zh y):y):2. 一般情況下，每經(jīng)過一趟“起泡”，“i 減一”，但并不是(b shi)每趟都如此。例如例如(lr):52319782553157989i=7i=6for (j = 1; j i; j+) if (Rj+1.key Rj.key) 13i=21. 起泡排序的結(jié)束條件為， 最后一趟沒有進(jìn)行最后一趟沒有進(jìn)行“交換記錄交換記錄”。第32頁/共105頁第三十三頁，共105頁。時(shí)間時(shí)間(shjin)(shjin)分析分析: :最好的情況（關(guān)鍵字在記錄最好的情況（關(guān)鍵字在記錄(jl)序列中順序有序）：序列中順序有

17、序）： 只需進(jìn)行一趟起泡只需進(jìn)行一趟起泡“比較比較(bjio)”的次數(shù)：的次數(shù)：最壞的情況（關(guān)鍵字在記錄序列中逆序有序）：最壞的情況（關(guān)鍵字在記錄序列中逆序有序）： 需進(jìn)行需進(jìn)行n-1趟起泡趟起泡“比較比較”的次數(shù)：的次數(shù)：0“移動(dòng)移動(dòng)”的次數(shù)：的次數(shù)：“移動(dòng)移動(dòng)”的次數(shù)：的次數(shù)：n-12) 1() 1(2nnini2) 1(3) 1(32nnini第33頁/共105頁第三十四頁，共105頁。二、一趟快速二、一趟快速(kui s)排序（一次劃分）排序（一次劃分）目標(biāo)：找一個(gè)記錄，以它的關(guān)鍵字作為目標(biāo)：找一個(gè)記錄，以它的關(guān)鍵字作為“樞軸樞軸”，凡其關(guān)鍵字小于樞軸的記錄均，凡其關(guān)鍵字小于樞軸的記錄

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

19、關(guān)鍵字 將 Rlow.key 和 樞軸的關(guān)鍵字進(jìn)行比較(bjio)，要求Rlow.key 樞軸的關(guān)鍵字high23low80high14low52例如例如R052lowhighhighhighlow第35頁/共105頁第三十六頁，共105頁。 可見，經(jīng)過“一次劃分” ，將關(guān)鍵字序列(xli) 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，它們(t men)的初值分別為： s 和 t， 之后逐漸減小 high，增加 low，

20、并保證 Rhigh.key52，和 Rlow.key52,否則(fuz)進(jìn)行記錄的“交換”。第36頁/共105頁第三十七頁，共105頁。int Partition (RedType& R, int low, int high) pivotkey = Rlow.key; while (lowhigh) while (low=pivotkey) -high; RlowRhigh; while (lowhigh & Rlow.key=pivotkey) +low; RlowRhigh; return low; / 返回返回(fnhu)樞軸所在位置樞軸所在位置 / Partition第

21、37頁/共105頁第三十八頁，共105頁。int Partition (RedType R, int low, int high) / Partition R0 = Rlow; pivotkey = Rlow.key; / 樞軸(sh zhu) while (lowhigh) while(low=pivotkey) - high; / 從右向左搜索從右向左搜索(su su)Rlow = Rhigh;while (lowhigh & Rlow.key=pivotkey) + low; / 從左向右搜索從左向右搜索(su su)Rhigh = Rlow;Rlow = R0; return

22、low;第38頁/共105頁第三十九頁，共105頁。三、快速三、快速(kui s)排序排序 首先對無序的記錄序列進(jìn)行“一次劃分”，之后分別對分割所得兩個(gè)(lin )子序列“遞歸”進(jìn)行快速排序。無 序 的 記 錄 序 列無序記錄(jl)子序列(1)無序子序列(2)樞軸樞軸一次劃分分別進(jìn)行快速排序第39頁/共105頁第四十頁，共105頁。void QSort (RedType & R, int s, int t ) / 對記錄序列對記錄序列Rs.t進(jìn)行進(jìn)行(jnxng)快速排序快速排序 if (s t-1) / 長度大于長度大于1 / QSortpivotloc = Partition(R

23、, s, t); / 對 Rs.t 進(jìn)行(jnxng)一次劃分QSort(R, s, pivotloc-1); / 對低子序列(xli)遞歸排序，pivotloc是樞軸位置QSort(R, pivotloc+1, t); / 對高子序列遞歸排序第40頁/共105頁第四十一頁，共105頁。void QuickSort( SqList & L) / 對順序表進(jìn)行對順序表進(jìn)行(jnxng)快速排序快速排序 QSort(L.r, 1, L.length); / QuickSort 第一次調(diào)用函數(shù) Qsort 時(shí)，待排序(pi x)記錄序列的上、下界分別為 1 和 L.length。第41頁/共

24、105頁第四十二頁，共105頁。四、快速四、快速(kui s)排序的時(shí)間分析排序的時(shí)間分析假設(shè)一次劃分所得樞軸位置 i=k，則對n 個(gè)記錄進(jìn)行(jnxng)快排所需時(shí)間：其中 Tpass(n)為對 n 個(gè)記錄(jl)進(jìn)行一次劃分所需時(shí)間。 若待排序列中記錄的關(guān)鍵字是隨機(jī)分布的，則 k 取 1 至 n 中任意一值的可能性相同T(n) = Tpass(n) + T(k-1) + T(n-k)第42頁/共105頁第四十三頁，共105頁。nkavgavgavgknTkTnCnnT1)() 1(1)(設(shè) Tavg(1)b則可得結(jié)果(ji gu)：) 1ln() 1)(22()(nncbnTavg結(jié)論結(jié)論

25、: 快速快速(kui s)排序的時(shí)間復(fù)雜度為排序的時(shí)間復(fù)雜度為O(nlogn)由此可得快速排序(pi x)所需時(shí)間的平均值為：第43頁/共105頁第四十四頁，共105頁。 若待排記錄的初始狀態(tài)為按關(guān)鍵字有序時(shí)，若待排記錄的初始狀態(tài)為按關(guān)鍵字有序時(shí)，快速排序快速排序(pi x)將蛻化為起泡排序?qū)⑼懟癁槠鹋菖判?pi x)，其時(shí)間復(fù)雜度為其時(shí)間復(fù)雜度為O(n2)。 為避免出現(xiàn)這種情況，需在進(jìn)行一次劃分之前(zhqin)，進(jìn)行“予處理”，即： 先對 R(s).key, R(t).key 和 R(s+t)/2. key，進(jìn)行相互比較(bjio)，然后取關(guān)鍵字為 “三者之中”的記錄為樞軸記錄。第44頁/

26、共105頁第四十五頁，共105頁。10.4 堆堆 排排 序序簡簡 單單 選選 擇擇 排排 序序堆堆 排排 序序第45頁/共105頁第四十六頁，共105頁。一、簡單一、簡單(jindn)選擇排序選擇排序假設(shè)排序過程中，待排記錄(jl)序列的狀態(tài)為：有序序列(xli)R1.i-1無序序列 Ri.n 第 i 趟簡單選擇排序從中選出關(guān)鍵字最小的記錄有序序列R1.i無序序列 Ri+1.n第46頁/共105頁第四十七頁，共105頁。簡單(jindn)選擇排序的算法描述如下：void SelectSort (Elem R, int n ) / 對記錄序列對記錄序列R1.n作簡單作簡單(jindn)選擇排序。

27、選擇排序。 for (i=1; i0; -i ) HeapAdjust ( H.r, i, H.length ); / 建大頂堆for ( i=H.length; i1; -i ) H.r1H.ri; / 將堆頂記錄將堆頂記錄(jl)和當(dāng)前未經(jīng)排序子序列和當(dāng)前未經(jīng)排序子序列 / H.r1.i中最后一個(gè)記錄中最后一個(gè)記錄(jl)相互交換相互交換 HeapAdjust(H.r, 1, i-1); / 對對 H.r1 進(jìn)行篩選進(jìn)行篩選第52頁/共105頁第五十三頁，共105頁。如何如何(rh)“建堆建堆”？兩個(gè)兩個(gè)(lin )問題問題:如何如何(rh)“篩選篩選”？定義堆類型為定義堆類型為:type

28、def SqList HeapType; / 堆采用順序表表示之第53頁/共105頁第五十四頁，共105頁。所謂“篩選(shixun)”指的是，對一棵左/右子樹均為堆的完全二叉樹，“調(diào)整”根結(jié)點(diǎn)使整個(gè)二叉樹也成為一個(gè)堆。堆堆篩選篩選(shixun)第54頁/共105頁第五十五頁，共105頁。98814973556412362740例如例如(lr):是大頂堆是大頂堆12但在 98 和 12 進(jìn)行(jnxng)互換之后，它就不是堆了，因此，需要對它進(jìn)行(jnxng)“篩選”。98128173641298比較比較比較第55頁/共105頁第五十六頁，共105頁。void HeapAdjust (Rcd

29、Type &R, int s, int m) / 已知已知 Rs.m中記錄的關(guān)鍵字除中記錄的關(guān)鍵字除 Rs 之外之外均均 / 滿足堆的特征，本函數(shù)自上而下調(diào)整滿足堆的特征，本函數(shù)自上而下調(diào)整(tiozhng) Rs 的的 / 關(guān)鍵字，使關(guān)鍵字，使 Rs.m 也成為一個(gè)大頂堆也成為一個(gè)大頂堆 / HeapAdjustrc = Rs; / 暫存 Rs for ( j=2*s; j= Rj.key ) break; / 再作再作“根根”和和“子樹根子樹根”之間的比之間的比較較(bjio) / 若若“=”成立，則說明已找到成立，則說明已找到 rc 的插的插 / 入位置入位置 s ，不需要繼續(xù)往

30、下調(diào)，不需要繼續(xù)往下調(diào)整整Rs = Rj; s = j; / 否則記錄否則記錄(jl)上移，尚需繼續(xù)往下調(diào)整上移，尚需繼續(xù)往下調(diào)整if ( jm & Rj.keyRj+1.key ) +j; / 左左/右右“子樹根子樹根”之間先進(jìn)行相互比較之間先進(jìn)行相互比較 / 令令 j 指示關(guān)鍵字較大記錄指示關(guān)鍵字較大記錄(jl)的位的位置置第57頁/共105頁第五十八頁，共105頁。建堆是一個(gè)建堆是一個(gè)(y )從下往上進(jìn)行從下往上進(jìn)行“篩選篩選”的過程。的過程。40554973816436122798例如例如: 排序之前排序之前(zhqin)的關(guān)鍵字序列為的關(guān)鍵字序列為12368173499881

31、7355 現(xiàn)在，左/右子樹都已經(jīng)調(diào)整(tiozhng)為堆，最后只要調(diào)整(tiozhng)根結(jié)點(diǎn)，使整個(gè)二叉樹是個(gè)“堆”即可。98494064361227第58頁/共105頁第五十九頁，共105頁。堆排序的時(shí)間堆排序的時(shí)間(shjin)復(fù)雜度分析：復(fù)雜度分析：1. 對深度為對深度為 k 的堆，的堆，“篩選篩選”所需進(jìn)行的關(guān)鍵字所需進(jìn)行的關(guān)鍵字比較比較(bjio)的次數(shù)至多為的次數(shù)至多為2(k-1)；3. 調(diào)整調(diào)整“堆頂堆頂” n-1 次，總共進(jìn)行次，總共進(jìn)行(jnxng)的關(guān)鍵的關(guān)鍵 字比較的次數(shù)不超過字比較的次數(shù)不超過 2 (log2(n-1)+ log2(n-2)+ +log22) 2n(

32、log2n) 因此，堆排序的時(shí)間復(fù)雜度為O(nlogn)。2. 對 n 個(gè)關(guān)鍵字，建成深度為h(=log2n+1)的堆，所需進(jìn)行的關(guān)鍵字比較的次數(shù)至多 4n；第59頁/共105頁第六十頁，共105頁。10.5 歸歸 并并 排排 序序歸并排序的過程基于下列基本(jbn)思想進(jìn)行： 將兩個(gè)或兩個(gè)以上的有序子序列 “歸并” 為一個(gè)有序序列。第60頁/共105頁第六十一頁，共105頁。在內(nèi)部(nib)排序中，通常采用的是2-路歸并排序。即：將兩個(gè)位置相鄰的記錄有序子序列歸并為一個(gè)記錄(jl)的有序序列。有有 序序 序序 列列 Rl.n有序子序列有序子序列(xli) Rl.m有序子序列有序子序列 Rm+

33、1.n這個(gè)操作對順序表而言，是輕而易舉的。第61頁/共105頁第六十二頁，共105頁。void Merge (RcdType SR, RcdType &TR, int i, int m, int n) / 將有序的記錄將有序的記錄(jl)序列序列 SRi.m 和和 SRm+1.n / 歸并為有序的記錄歸并為有序的記錄(jl)序列序列 TRi.n / Mergefor (j=m+1, k=i; i=m & j=n; +k) / 將將SR中記錄中記錄(jl)由小到大地并入由小到大地并入TR if (SRi.key=SRj.key) TRk = SRi+; else TRk = SR

34、j+; 第62頁/共105頁第六十三頁，共105頁。if (i=m) TRk.n = SRi.m; / 將剩余將剩余(shngy)的的 SRi.m 復(fù)制到復(fù)制到 TRif (j=n) TRk.n = SRj.n; / 將剩余將剩余(shngy)的的 SRj.n 復(fù)制到復(fù)制到 TR第63頁/共105頁第六十四頁，共105頁。歸并歸并(gubng)排序的算法排序的算法如果記錄無序序列 Rs.t 的兩部分 Rs.(s+t)/2 和 R(s+t)/2+1.t分別按關(guān)鍵字有序，則利用上述歸并算法很容易(rngy)將它們歸并成整個(gè)記錄序列是一個(gè)有序序列。 由此，應(yīng)該先分別對這兩部分進(jìn)行(jnxng) 2-

35、路歸并排序。第64頁/共105頁第六十五頁，共105頁。例如例如(lr)：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, 68, 80 23第65頁/共105頁第六十六頁，共105頁。void Msort ( RcdType SR, RcdType &TR1, int s, int t ) / 將將SRs.t 歸并歸并(gubng)排序?yàn)榕判驗(yàn)?TR1s.t if (s= =t

36、) TR1s=SRs; else / Msort 第66頁/共105頁第六十七頁，共105頁。m = (s+t)/2; / 將SRs.t平分為(fn wi)SRs.m和SRm+1.tMsort (SR, TR2, s, m); / 遞歸地將SRs.m歸并(gubng)為有序的TR2s.mMsort (SR, TR2, m+1, t); /遞歸地SRm+1.t歸并(gubng)為有序的TR2m+1.tMerge (TR2, TR1, s, m, t); / 將TR2s.m和TR2m+1.t歸并到TR1s.t第67頁/共105頁第六十八頁，共105頁。void MergeSort (SqList

37、&L) / 對順序?qū)樞?shnx)表表 L 作作2-路歸并排序路歸并排序 MSort(L.r, L.r, 1, L.length); / MergeSort容易看出，對 n 個(gè)記錄進(jìn)行歸并(gubng)排序的時(shí)間復(fù)雜度為(nlogn)。即： 每一趟歸并(gubng)的時(shí)間復(fù)雜度為 O(n)， 總共需進(jìn)行 log2n 趟。第68頁/共105頁第六十九頁，共105頁。10.6 基基 數(shù)數(shù) 排排 序序第69頁/共105頁第七十頁，共105頁?；鶖?shù)排序(pi x)是一種借助“多關(guān)鍵字排序(pi x)”的思想來實(shí)現(xiàn)“單關(guān)鍵字排序(pi x)”的內(nèi)部排序(pi x)算法。多關(guān)鍵字的排序多關(guān)鍵字的

38、排序(pi x)鏈?zhǔn)交鶖?shù)排序鏈?zhǔn)交鶖?shù)排序第70頁/共105頁第七十一頁，共105頁。一、多關(guān)鍵字的排序一、多關(guān)鍵字的排序(pi x) n 個(gè)記錄個(gè)記錄(jl)的序列的序列 R1, R2, ，Rn對關(guān)鍵字對關(guān)鍵字 (Ki0, Ki1,Kid-1) 有序是指：有序是指： 其中其中(qzhng): K0 (qzhng): K0 被稱為被稱為 “ “最主最主”位關(guān)鍵字位關(guān)鍵字Kd-1 被稱為被稱為 “最次最次”位關(guān)鍵字位關(guān)鍵字 對于序列中任意兩個(gè)記錄 Ri 和 Rj(1ijn) 都滿足滿足下列(詞典詞典)有序有序關(guān)系： (Ki0, Ki1, , ,Kid-1) ) (Kj0, Kj1, , ,Kjd-

39、1) )第71頁/共105頁第七十二頁，共105頁。 實(shí)現(xiàn)(shxin)多關(guān)鍵字排序通常有兩種作法:最低位優(yōu)先最低位優(yōu)先(yuxin)LSD(yuxin)LSD法法最高位優(yōu)先最高位優(yōu)先(yuxin)MSD(yuxin)MSD法法第72頁/共105頁第七十三頁，共105頁。先對先對K0K0進(jìn)行排序，并按進(jìn)行排序，并按 K0 K0 的不的不同值將記錄序列分成若干子序列同值將記錄序列分成若干子序列之后之后(zhhu)(zhhu)，分別對，分別對 K1 K1 進(jìn)行進(jìn)行排序，排序，.， 依次類推，直至依次類推，直至最后對最次位關(guān)鍵字排序完成為最后對最次位關(guān)鍵字排序完成為止。止。第73頁/共105頁第七十

40、四頁，共105頁。 先對 Kd-1 進(jìn)行(jnxng)排序，然后對 Kd-2 進(jìn)行(jnxng)排序，依次類推，直至對最主位關(guān)鍵字 K0 排序完成為止。 排序過程中不需要根據(jù) “前一個(gè)” 關(guān)鍵字的排序結(jié)果，將記錄序列(xli)分割成若干個(gè)(“前一個(gè)”關(guān)鍵字不同的)子序列(xli)。第74頁/共105頁第七十五頁，共105頁。例如例如: :學(xué)生記錄學(xué)生記錄(jl)(jl)含三個(gè)關(guān)鍵含三個(gè)關(guān)鍵字字: :系別、班號和班內(nèi)的序列號，其中以系系別、班號和班內(nèi)的序列號，其中以系別為最主位關(guān)鍵字。別為最主位關(guān)鍵字。 無序(w x)序列對對K2排序排序(pi x)對對K1排序排序?qū)0排序排序3,2,301

41、,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的排序過程如下:第75頁/共105頁第七十六頁，共105頁。二、鏈?zhǔn)交鶖?shù)排序二、鏈?zhǔn)交鶖?shù)排序假如多關(guān)鍵字的記錄序列中，每個(gè)關(guān)鍵字的取值范圍相同(xin tn)，則按LSD法進(jìn)行排序時(shí)，可以采用“分配-收集”的方法，其好處是不需要進(jìn)行關(guān)鍵字間的比較。對于數(shù)字型或字符型的單關(guān)鍵字，可以看成是由多個(gè)數(shù)位或多個(gè)字符構(gòu)成的多關(guān)鍵字，此時(shí)可以采用這種“分配-收集”的辦法進(jìn)行(

42、jnxng)排序，稱作基數(shù)排序法。第76頁/共105頁第七十七頁，共105頁。例如例如(lr)：對下列這組關(guān)鍵字：對下列這組關(guān)鍵字 209, 386, 768, 185, 247, 606, 230, 834, 539 首先按其 “個(gè)位數(shù)” 取值分別為 0, 1, , 9 “分配” 成 10 組，之后按從 0 至 9 的順序(shnx)將 它們 “收集” 在一起； 然后按其 “十位數(shù)” 取值分別為 0, 1, , 9 “分配” 成 10 組，之后再按從 0 至 9 的順序?qū)⑺鼈?“收集(shuj)” 在一起；最后按其“百位數(shù)”重復(fù)一遍上述操作。第77頁/共105頁第七十八頁，共105頁。在計(jì)算

43、機(jī)上實(shí)現(xiàn)基數(shù)排序時(shí)，為減少所需輔助存儲(chǔ)空間，應(yīng)采用(ciyng)鏈表作存儲(chǔ)結(jié)構(gòu)，即鏈?zhǔn)交鶖?shù)排序，具體作法為： 待排序(pi x)記錄以指針相鏈，構(gòu)成一個(gè)鏈表；“分配分配” ” 時(shí)，按當(dāng)前時(shí)，按當(dāng)前“關(guān)鍵字位關(guān)鍵字位”所取所取值，將記錄分配到不同的值，將記錄分配到不同的 “ “鏈隊(duì)列鏈隊(duì)列(duli)” (duli)” 中，每個(gè)隊(duì)列中，每個(gè)隊(duì)列(duli)(duli)中記錄的中記錄的 “關(guān)鍵字位關(guān)鍵字位” ” 相同；相同；“收集”時(shí)，按當(dāng)前關(guān)鍵字位取值從小到大將各隊(duì)列首尾相鏈成一個(gè)鏈表;對每個(gè)關(guān)鍵字位均重復(fù) 2) 和 3) 兩步。第78頁/共105頁第七十九頁，共105頁。例如(lr)：p369

44、367167239237138230139進(jìn)行進(jìn)行(jnxng)第一次分配第一次分配進(jìn)行進(jìn)行(jnxng)第一次收集第一次收集f0 r0f7 r7f8 r8f9 r9p230230367 167237367167237 138368239139369 239139138第79頁/共105頁第八十頁，共105頁。進(jìn)行進(jìn)行(jnxng)第二次分配第二次分配p230237138239139p230367167237138368239139f3 r3f6 r6230 237138239139367 167368367167368進(jìn)行(jnxng)第二次收集第80頁/共105頁第八十一頁，共105頁。

45、進(jìn)行第三次收集之后便得到記錄(jl)的有序序列f1 r1p230237138239139367167368進(jìn)行進(jìn)行(jnxng)第三次分配第三次分配f2 r2f3 r3138 139167230 237239367 368p138139167230237239367368第81頁/共105頁第八十二頁，共105頁。提醒提醒(t xng)注意：注意：“分配分配”和和“收集收集”的實(shí)際操作僅的實(shí)際操作僅為修改鏈表中的指針和設(shè)置為修改鏈表中的指針和設(shè)置(shzh)隊(duì)隊(duì)列的頭、尾指針；列的頭、尾指針；為查找使用，該鏈表尚需應(yīng)用算法為查找使用，該鏈表尚需應(yīng)用算法(sun f)Arrange 將它調(diào)整為有

46、序表。將它調(diào)整為有序表。第82頁/共105頁第八十三頁，共105頁。 基數(shù)排序的時(shí)間(shjin)復(fù)雜度為O(d(n+rd)其中(qzhng)：分配為O(n) 收集為O(rd)(rd為“基”) d為“分配-收集”的趟數(shù)第83頁/共105頁第八十四頁，共105頁。10.7 各種排序方法的綜合各種排序方法的綜合(zngh)比較比較第84頁/共105頁第八十五頁，共105頁。一、時(shí)間一、時(shí)間(shjin)性能性能1. 平均的時(shí)間平均的時(shí)間(shjin)性能性能基數(shù)排序基數(shù)排序時(shí)間時(shí)間(shjin)復(fù)雜度為復(fù)雜度為 O(nlogn)：快速排序、堆排序和歸并排序快速排序、堆排序和歸并排序時(shí)間復(fù)雜度為時(shí)間

47、復(fù)雜度為 O(n2)：直接插入排序、起泡排序和直接插入排序、起泡排序和簡單選擇排序簡單選擇排序時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為 O(n):第85頁/共105頁第八十六頁，共105頁。2. 當(dāng)待排記錄序列當(dāng)待排記錄序列(xli)按關(guān)鍵字順序有按關(guān)鍵字順序有序時(shí)序時(shí)3. 簡單簡單(jindn)選擇排序、堆排序和歸選擇排序、堆排序和歸并排序的時(shí)間性能不隨記錄序列中關(guān)鍵并排序的時(shí)間性能不隨記錄序列中關(guān)鍵字的分布而改變。字的分布而改變。 直接插入排序和起泡排序能達(dá)到(d do)O(n)的時(shí)間復(fù)雜度， 快速排序的時(shí)間性能蛻化為O(n2) 。第86頁/共105頁第八十七頁，共105頁。二、空間二、空間(kngjin

48、)性能性能指的是排序過程中所需的輔助空間(kngjin)大小1. 所有所有(suyu)的簡單排序方法的簡單排序方法(包括：包括：直接插入、直接插入、起泡和簡單選擇起泡和簡單選擇) 和堆排序的空間復(fù)雜度和堆排序的空間復(fù)雜度為為O(1)；2. 快速排序?yàn)榭焖倥判驗(yàn)镺(logn)，為遞歸程序執(zhí)行過程中，棧所需的輔助空間；第87頁/共105頁第八十八頁，共105頁。3. 歸并排序歸并排序(pi x)所需輔助空間最所需輔助空間最多，其空間復(fù)雜度為多，其空間復(fù)雜度為 O(n);4. 鏈?zhǔn)交鶖?shù)排序需附設(shè)隊(duì)列首尾指針鏈?zhǔn)交鶖?shù)排序需附設(shè)隊(duì)列首尾指針(zhzhn)，則空間復(fù)雜度為，則空間復(fù)雜度為 O(rd)。第8

49、8頁/共105頁第八十九頁，共105頁。三、排序三、排序(pi x)方法的穩(wěn)定性能方法的穩(wěn)定性能 1. 穩(wěn)定的排序方法指的是，對于兩個(gè)關(guān)鍵字相等的記錄，它們在序列中的相對位置(wi zhi)，在排序之前和經(jīng)過排序之后，沒有改變。 2. 當(dāng)對多關(guān)鍵字的記錄序列進(jìn)行當(dāng)對多關(guān)鍵字的記錄序列進(jìn)行LSD方方法法(fngf)排序時(shí)，必須采用穩(wěn)定的排序排序時(shí)，必須采用穩(wěn)定的排序方法方法(fngf)。排序之前 : Ri(K) Rj(K) 排序之后 : Ri(K) Rj(K) 第89頁/共105頁第九十頁，共105頁。例如例如(lr)： 排序(pi x)前 ( 56, 34, 47, 23, 66, 18, 8

50、2, 47 )若排序后得到結(jié)果 ( 18, 23, 34, 47, 47, 56, 66, 82 )則稱該排序方法(fngf)是穩(wěn)定的;若排序后得到結(jié)果 ( 18, 23, 34, 47, 47, 56, 66, 82 )則稱該排序方法是不穩(wěn)定不穩(wěn)定的。第90頁/共105頁第九十一頁，共105頁。 3. 對于對于(duy)不穩(wěn)定的排序方法，只不穩(wěn)定的排序方法，只要能舉出一個(gè)實(shí)例說明即可。要能舉出一個(gè)實(shí)例說明即可。 4. 快速排序快速排序(pi x)、堆排序、堆排序(pi x)和和希爾排序希爾排序(pi x)是不穩(wěn)定的排序是不穩(wěn)定的排序(pi x)方法。方法。例如例如 : 對對 4, 3, 4,

51、 2 進(jìn)行進(jìn)行(jnxng)快快速排序，速排序， 得到得到 2, 3, 4, 4 第91頁/共105頁第九十二頁，共105頁。四、關(guān)于四、關(guān)于“排序方法排序方法(fngf)的時(shí)間復(fù)雜度的時(shí)間復(fù)雜度的下限的下限” 本章討論的各種排序方法，除基數(shù)排序外，其它方法都是基于“比較(bjio)關(guān)鍵字”進(jìn)行排序的排序方法。 可以證明， 這類排序(pi x)法可能達(dá)到的最快的時(shí)間復(fù)雜度為O(nlogn)。 (基數(shù)排序(pi x)不是基于“比較關(guān)鍵字”的排序(pi x)方法，所以它不受這個(gè)限制。)第92頁/共105頁第九十三頁，共105頁。10.8外外 部部 排排 序序第93頁/共105頁第九十四頁，共105

52、頁。一一. 問題問題(wnt)的提出的提出 待排序的記錄數(shù)量很大，不能待排序的記錄數(shù)量很大，不能一次裝入內(nèi)存，則無法利用前幾節(jié)一次裝入內(nèi)存，則無法利用前幾節(jié)討論的排序方法討論的排序方法 (否則否則(fuz)將引將引起頻繁訪問內(nèi)存起頻繁訪問內(nèi)存)；第94頁/共105頁第九十五頁，共105頁。 對外存中數(shù)據(jù)對外存中數(shù)據(jù)(shj)的讀的讀/寫是以寫是以“數(shù)據(jù)數(shù)據(jù)(shj)塊塊”為單位進(jìn)行的；為單位進(jìn)行的； 讀讀/寫外存中一個(gè)寫外存中一個(gè)“數(shù)據(jù)數(shù)據(jù)(shj)塊塊”的數(shù)的數(shù)據(jù)據(jù)(shj)所需要的時(shí)間為：所需要的時(shí)間為： TI/O = tseek + tla + n twm 其中其中 tseek 為尋查時(shí)間為尋查時(shí)間(查找該數(shù)據(jù)查找該數(shù)據(jù)(shj)塊所在磁道塊所在磁道) tla 為等待為等待(延遲延遲)時(shí)間時(shí)間 n twm 為傳輸數(shù)據(jù)為傳輸數(shù)據(jù)(