數(shù)據(jù)結構教學課件：第7章 排序

1、概述插入排序交換排序選擇排序歸并排序基數(shù)排序外排序第7章 排序1概述數(shù)據(jù)表(datalist): 它是待排序數(shù)據(jù)對象的有限集合。關鍵碼(key): 通常數(shù)據(jù)對象有多個屬性域, 即多個數(shù)據(jù)成員組成, 其中有一個屬性域可用來區(qū)分對象, 作為排序依據(jù)。該域即為關鍵碼。每個數(shù)據(jù)表用哪個屬性域作為關鍵碼，要視具體的應用需要而定。2排序：將一組雜亂無章的數(shù)據(jù)按一定的規(guī)律順次排列起來。排序問題確切定義：給定一組記錄r1, r2, rn，其排序碼分別為k1, k2, ，kn，將這些記錄排成順序為rs1,rs2,rsn 的一個序列S，滿足條件ks1ks2ksn 或ks1ks2 ksn 。3排序的目的：便于查找內

2、排序與外排序: 內排序是指在排序期間數(shù)據(jù)對象全部存放在內存的排序；外排序是指在排序期間全部對象個數(shù)太多，不能同時存放在內存，必須根據(jù)排序過程的要求，不斷在內、外存之間移動的排序。4排序算法好壞的衡量： 1）時間效率 2）空間效率 3）穩(wěn)定性排序的時間開銷: 排序的時間開銷是衡量算法好壞的最重要的標志。排序的時間開銷可用算法執(zhí)行中的數(shù)據(jù)比較次數(shù)與數(shù)據(jù)移動次數(shù)來衡量。算法運行時間代價的大略估算一般都按平均情況進行估算。對于那些受對象排序碼序列初始排列及對象個數(shù)影響較大的，需要按最好情況和最壞情況進行估算。5算法執(zhí)行時所需的附加存儲: 評價算法好壞的另一標準。排序算法的穩(wěn)定性: 如果在對象序列中有兩

3、 個對象ri和rj, 它們的排序碼 ki = kj , 且在排序之前, 對象ri排在rj前面。如果在排序之后, 對象ri仍在對象rj的前面, 則稱這個排序方法是穩(wěn)定的, 否則稱這個排序方法是不穩(wěn)定的。6插入排序 (Insert Sorting) 基本方法是 : 每步將一個待排序的對象, 按其排序碼大小, 插入到前面已經(jīng)排好序的一組對象的適當位置上, 直到對象全部插入為止。共做n趟排序，第i趟排序的過程如下:有序序列r1.i-1ri無序序列 ri.n有序序列r1.i無序序列 ri+1.n7直接插入排序 (Insert Sort)基本思想是 : 當插入第i (i 1) 個對象時, 前面的V0, V

4、1, , Vi-1已經(jīng)排好序。這時, 用Vi的排序碼與Vi-1, Vi-2, 的排序碼順序進行比較, 找到插入位置即將Vi插入, 原來位置上的對象向后順移。插入過程分為兩步:1、利用 “順序查找”實現(xiàn)“在V1.i-1中查找Vi的插入位置”2、插入8例：關鍵字序列T= （21，25，49，25*，16，08），請寫出直接插入排序的具體實現(xiàn)過程。*表示后一個25解：假設該序列已存入一維數(shù)組R7中，將R0作為緩沖或暫存單元（Temp）。則程序執(zhí)行過程為：i=121254925*16080 1 2 3 4 5 6暫存21i=2i=3i=5i=4i=625252549494925*25*49161625

5、*08084921254925*21初態(tài)：164925*25211608完成!考慮:若記錄是鏈表結構,插入排序是否可行?直接插入不僅可行，而且還無需移動元素，時間效率更高！9設待排序對象個數(shù)為currentSize = n, 則該算法的主程序執(zhí)行n-1趟。排序碼比較次數(shù)和對象移動次數(shù)與對象排序碼的初始排列有關。最好情況下（關鍵字在記錄序列中順序有序）, 每趟只需與前面有序對象序列的最后一個對象比較1次, 移動2次對象, 總的排序 碼比較次數(shù)為 n-1, 對象移動次數(shù)為2(n-1) 。直接插入排序的算法分析10 最壞情況下（關鍵字在記錄序列中逆序有序）, 第 i 趟時第 i 個對象必須與前面 i

6、 個對象都做排序碼比較, 并且每做1次比較就要做1次數(shù)據(jù)移動。則總排序碼比較次數(shù)KCN和對象移動次數(shù)RMN分別為平均情況下排序的時間復雜度為 O(n2)。直接插入排序是一種穩(wěn)定的排序方法。11折半插入排序 (Binary Insertsort)有序序列R1.i-1Ri無序序列 Ri.n基本思想：因為 R1.i-1 是一個按關鍵字有序的有序序列，則可以利用折半查找實現(xiàn)“在R1.i-1中查找Ri的插入位置”，如此實現(xiàn)的插入排序為折半插入排序。1214 36 49 52 8058 61 23 97 75ilowhighmmlowlowmhigh14 36 49 52 58 61 80 23 97 7

7、5ilowhighmhighmhighmlow例如:再如:插入位置插入位置L.rL.r13折半搜索比順序搜索查找快, 所以折半插入排序就平均性能來說比直接插入排序要快。它所需的排序碼比較次數(shù)與待排序對象序列的初始排列無關, 僅依賴于對象個數(shù)。在插入第 i 個對象時, 需要經(jīng)過 log2i +1 次排序碼比較, 才能確定它應插入的位置。因此, 將 n 個對象(為推導方便, 設為 n=2k )用折半插入排序所進行的排序碼比較次數(shù)為：折半插入排序是一個穩(wěn)定的排序方法。14當 n 較大時, 總排序碼比較次數(shù)比直接插入排序的最壞情況要好得多, 但比其最好情況要差。在對象的初始排列已經(jīng)按排序碼排好序或接近

8、有序時, 直接插入排序比折半插入排序執(zhí)行的排序碼比較次數(shù)要少。折半插入排序的對象移動次數(shù)與直接插入排序相同, 依賴于對象的初始排列。討論：若記錄是鏈表結構，折半插入排序可行嗎？鏈表無法“折半”！15希爾排序 (Shell Sort)希爾排序方法又稱為縮小增量排序。該方法的基本思想是 :對待排記錄序列先作“宏觀”調整，再作“微觀”調整。 每一趟排序：將待排序序列分成若干子序列。子序列的構成不是簡單地“逐段分割”，而是將相隔某個增量的記錄組成一個子序列，然后對每個子序列進行插入排序。 下一趟開始前讓增量逐趟縮短（例如依次取5,3,1），直到增量1,用直接插入法做微觀調整。16例：關鍵字序列 T=(

9、49，38，65，97, 76, 13, 27, 49*，55, 04），請寫出希爾排序的具體實現(xiàn)過程。分析：開始時dk 的值較大，子序列中的對象較少，排序速度較快,讓關鍵字值小的元素能很快前移，使序列基本有序；隨著排序進展，dk 值逐漸變小，子序列中對象個數(shù)逐漸變多，由于前面工作的基礎，大多數(shù)對象已基本有序，只做局部調整即可，所以排序速度仍然很快。380123456789gap4938659776132749*5504531初態(tài)：第1趟 第2趟 第3趟 4913134938276549*975576042738 65 49*9755135576045513270427044949*4949*

10、763876 65 65 9797551327044949*3876 65 9713 27 0449* 76 97 ri17Gap的取法有多種。最初 shell 提出取 gap = n/2，gap = gap/2，直到gap = 1。knuth 提出取 gap = gap/3 +1。還有人提出都取奇數(shù)為好，也有人提出各 gap 互質為好。對特定的待排序對象序列，可以準確地估算排序碼的比較次數(shù)和對象移動次數(shù)。18交換排序 ( Exchange Sort ) 基本思想是兩兩比較待排序對象的排序碼,如果發(fā)生逆序(即排列順序與排序后的次序正好相反)，則交換之。直到所有對象都排好序為止。19起泡排序 (

11、Bubble Sort)基本方法是：設待排序對象序列中的對象個數(shù)為 n。最多作 n-1 趟，i = 1, 2, , n-1 。在第 i 趟中從后向前，j = n-1, n-2, , i，順次兩兩比較Vj-1.key和Vj.key。如果發(fā)生逆序，則交換Vj-1和Vj。優(yōu)點：每趟結束時，不僅能冒出一個最小值 (最大值)到最前(后)面位置，還能同時部分理順其他元素；一旦下趟沒有交換發(fā)生，還可以提前結束排序。20例如:2553157989i=613i=5i=n1221第i趟對待排序對象序列Vi-1,Vi,Vn-1進行排序, 結果將該序列中排序碼最小(大)的對象交換到序列的第一個位置(i-1), 其它對

12、象也都向排序的最終位置移動。在個別情形, 對象可能在排序中途向相反的方向移動。最多做n-1趟起泡就能把所有對象排好序。起泡排序是一個穩(wěn)定的排序方法。22在對象的初始排列已經(jīng)按排序碼從小到大排好序時,此算法只執(zhí)行一趟起泡,做n-1次排序碼比較,不移動對象。這是最好的情形。最壞的情形是算法執(zhí)行n-1趟起泡,第i趟 (1 i n) 做 n- i 次排序碼比較, 執(zhí)行 n-i 次對象交換。這樣在最壞情形下總的排序碼比較次數(shù)KCN和對象移動次數(shù)RMN為：23快速排序 (Quick Sort)基本思想是任取待排序對象序列中的某個對象 (例如取第一個對象) 作為基準, 按照該對象的排序碼大小, 將整個對象序

13、列劃分為左右兩個子序列： 左側子序列中所有對象的排序碼都小于或等于基準對象的排序碼 。右側子序列中所有對象的排序碼都大于基準對象的排序碼。24然后分別對這兩個子序列重復施行上述方法，直到每個子序列的元素只剩一個。此時便為有序序列了。優(yōu)點：因為每趟可以確定不止一個元素的位置，而且呈指數(shù)增加，所以特別快！25例：關鍵字序列 T=(21，25，49，25*，16，08），快速排序的算法步驟:( )21， 25， 49， 25*，16， 08初態(tài)：第1趟：第2趟：第3趟： 08， 16， 21，25* ， 25，(49)2108，16,，( )25* ，25，4908， (16)，21， 25* ，(

14、25，49)26算法quicksort是一個遞歸的算法, 其遞歸樹如圖所示。2125*25490816那么：一趟排序過程如何實現(xiàn)?27例：快速排序算法的一趟實現(xiàn)過程:21， 25， 49， 25*，16， 08初態(tài)：第1趟：(08，16)，21，(25*，25 ，49)21， 25， 49， 25*，16， 08初始序列： 0 1 2 3 4 5pivotposlowi21， 16， 49， 25*，25， 08循環(huán)4：pivotposi21， 16， 08， 25*，25， 49循環(huán)5：pivotpos(08 ，16)，21，(25*，25，49)出循環(huán)：pivotposlow28算法分析從

15、快速排序算法的遞歸樹可知, 快速排序的趟數(shù)取決于遞歸樹的高度。如果每次劃分對一個對象定位后, 該對象的左側子序列與右側子序列的長度相同, 則下 一步將是對兩個長度減半的子序列進行排序, 這是最理想的情況。29在 n個元素的序列中, 對一個對象定位所需時間為 O(n)。若設 T (n) 是對 n 個元素的序列進行排序所需的時間, 而且每次對一個對象正確定位后, 正好把序列劃分為長度相等的兩個子序列, 此時, 總的計算時間為：T(n) cn + 2T(n/2 ) / c 是一個常數(shù) cn + 2 ( cn/2 + 2T(n/4) ) = 2cn + 4T(n/4) 2cn + 4 ( cn/4 +

16、2T(n/8) ) = 3cn + 8T(n/8) cn log2n + nT(1) = O(n log2n )30快速排序是遞歸的，需要有一個棧存放每層遞歸調用時的指針和參數(shù)。最大遞歸調用層次數(shù)與遞歸樹的高度一致,理想情況為 log2(n+1) 。因此，要求存儲開銷為 O(log2n)。31在最壞的情況, 即待排序對象序列已經(jīng)按其排序碼從小到大排好序的情況下, 其遞歸樹成為單支樹, 每次劃分只得到一個比上一次少一個對象的子序列。必須經(jīng)過n-1 趟才能把所有對象定位, 而且第 i 趟需要經(jīng)過 n-i 次排序碼比較才能找到第 i 個對象的安放位置，總的排序碼比較次數(shù)將達到快速排序退化32用第一個

17、對象作為基準對象 快速排序退化的例子 08 16 21 25 25* 49080 1 2 3 4 5 pivot初始 16 21 25 25* 49 0816 21 25 25* 4921 08 1625 25 25* 49 08 16 21 25* 4925* 08 16 21 2549 08 16 21 25 25*i = 1i = 2i = 3i = 4i = 533其排序速度退化到簡單排序的水平, 比直接插入排序還慢。占用附加存儲(棧)將達到O(n)。改進辦法: 取每個待排序對象序列的第一個對象、最后一個對象和位置接近正中的 3 個對象，取其排序碼居中者作為基準對象。34快速排序是一種

18、不穩(wěn)定的排序方法。對于 n 較大的平均情況而言, 快速排序是“快速”的, 但是當 n 很小時, 這種排序方法往往比其它簡單排序方法還要慢。用居中排序碼對象作為基準對象 08 16 21 25 25* 490 1 2 3 4 5 pivot21初始 08 16 21 25 25* 490825* 08 16 21 25 25*49i = 1i = 235 基本思想是: 每一趟 (例如第 i 趟, i = 0, 1, , n-2) 在后面 n-i 個待排序對象中選出排序碼最小的對象, 作為有序對象序列的第 i 個對象。待到第 n-2 趟作完, 待排序對象只剩下1個, 就不用再選了。選擇排序有序序列

19、r1.i-1無序序列 ri.n有序序列r1.i無序序列 ri+1.nrirk其排序碼最小36基本步驟： 在一組對象 ViVn-1 中選擇具有最小排序碼的對象； 若它不是這組對象中的第一個對象, 則將它與這組對象中的第一個對象對調; 在這組對象中剔除這個具有最小排序碼的對象。在剩下的對象Vi+1Vn-1中重復執(zhí)行第、步, 直到剩余對象只有一個為止。直接選擇排序 (Select Sort)37例：關鍵字序列T= （21，25，49，25*，16，08），請給出簡單選擇排序的具體實現(xiàn)過程。原始序列： 21，25，49，25*，16，08第1趟第2趟第3趟第4趟第5趟08，25，49，25*，16，2

20、108，16, 49，25*，25，2108，16, 21，25*，25，4908，16, 21，25*，25，4908，16, 21，25*，25，4938討論：能否利用（或記憶）首趟的n-1次比較所得信息，從而盡量減少后續(xù)比較次數(shù)呢？ 能！錦標賽排序和堆排序！時間效率： O(n2)共n-1趟，第i趟比較n-i次。 空間效率： 無需任何附加單元！算法的穩(wěn)定性：不穩(wěn)定因為排序時，25*到了25的前面。算法分析39錦標賽排序 (Tournament Tree Sort)它的思想與體育比賽時的淘汰賽類似。首先取得 n 個對象的排序碼, 進行兩兩比較, 得到 n/2 個比較的優(yōu)勝者(排序碼小者),

21、作為第一步比較的結果保留下來。然后對這 n/2 個對象再進行排序碼的兩兩比較, , 如此重復, 直到選出一個排序碼最小的對象為止。40勝者樹的概念每次兩兩比較的結果是把排序碼小者作為優(yōu)勝者上升到雙親結點，稱這種比賽樹為勝者樹。位于最底層的葉結點叫做勝者樹的外結點，非葉結點稱為勝者樹的內結點。勝者樹最頂層是樹的根，表示最后選擇出來的具有最小排序碼的對象。4108Winner (勝者)2108086325*2121254925*160863r1初態(tài)：補足葉子結點，使其為滿二叉樹第一趟：勝者樹例：關鍵字序列T= （21，25，49，25*，16，08，63），請給出錦標賽排序的具體實現(xiàn)過程。42第二

22、趟：082108086325*2121254925*160863161616r2Winner (勝者)令其Active 0,不參與比較43令其Active 0,不參與比較第三趟：162116166325*2121254925*160863r3Winner (勝者)632144082108086325*2121254925*1608636321第四趟：r4Winner (勝者)25252545082108086325*2121254925*1608631616166321252525第五趟：r5Winner (勝者)25*25*46082108086325*2121254925*16086316

23、1616632125252525*25*第六趟：r6Winner (勝者)49494947082108086325*2121254925*160863161616632125252525*25*494949第七趟：r7Winner (勝者)6348錦標賽排序構成的勝者樹是滿的完全二叉樹, 其深度為 log2n , 其中 n 為待排序元素個數(shù)。除第一次選擇具有最小排序碼的對象需要進行 n-1 次排序碼比較外, 重構勝者樹選擇具有次小、再次小排序碼對象所需的排序碼比較次數(shù)均為 O(log2n)?？偱判虼a比較次數(shù)為O(nlog2n)。對象的移動次數(shù)不超過排序碼的比較次數(shù)，所以錦標賽排序總時間復雜度為

24、O(nlog2n)。49這種排序方法雖然減少了許多排序時間, 但是使用了較多的附加存儲。如果有 n 個對象，必須使用至少 2n-1 個結點來存放勝者樹。最多需要找到滿足 2k-1 n 2k 的k，使用 2*2k-1 個結點。每個結點包括排序碼、結點序號和比較標志三種信息。錦標賽排序是一個穩(wěn)定的排序方法。50堆 ( Heap )優(yōu)先級隊列 線性結構：隊尾插入，隊頭刪除 每次出隊列的是優(yōu)先權最高（低）的元素 數(shù)組表示，效率低堆排序51堆的定義098778456531532317012345678098778456531235317012345678完全二叉樹順序表示，滿足：Ki K2i+1 & K

25、i K2i+1 &Ki K2i+2 Ki K2i+252最小堆的類定義# define DefaultSize 10 ;template class MinHeap : public MinPQ private: Type * heap; /存放最小堆元素的數(shù)組 int CurrentSize; /最小堆當前元素個數(shù) int MaxHeapSize; /最多允許元素個數(shù) void FilterDown ( int i, int m ); /從 i 到m自頂向下進行調整成為最小堆 53 void FilterUp ( int i ); /從 i 到0自底向上進行調整成為最小堆public: Mi

26、nHeap ( int sz ); /構造函數(shù) : 建立空堆 MinHeap ( Type arr , int n ); /構造函數(shù) MinHeap ( ) delete heap; const MinHeap & operator = (const MinHeap &R) int Insert ( const Type& x ); /插入 int RemoveMin ( Type& x ); /刪除 54 int IsEmpty ( ) const /判堆空否 return CurrentSize = 0; int IsFull ( ) const /判堆滿否 return CurrentS

27、ize = MaxHeapSize; void MakeEmpty ( ) CurrentSize = 0; 55堆的建立1. 建一個空堆template MinHeap :MinHeap ( int maxSize ) /根據(jù)給定大小maxSize,建立堆對象 MaxHeapSize = DefaultSize maxSize ? maxSize : DefaultSize; /確定堆的大小 heap = new Type MaxHeapSize; CurrentSize = 0; 562. 復制數(shù)組并加以調整形成堆template MinHeap : MinHeap ( Type arr

28、, int n ) /根據(jù)給定數(shù)組中的數(shù)據(jù)和大小,建立堆對象 MaxHeapSize = DefaultSize = 0 ) /從下到上逐步擴大,形成堆 FilterDown ( currentPos, CurrentSize-1 ); /從currentPos開始,到CurrentSize止, /調整 currentPos-; 5317780923456587icurrentPos = i = 30123456758最小堆的向下調整算法template void MinHeap : FilterDown ( int start, int EndOfHeap ) int i = start,

29、j = 2*i+1; / j 是 i 的左子女 Type temp = heapi; while ( j = EndOfHeap ) if ( j heapj+1 ) j+; /兩子女中選小者 if ( temp.key = heapj.key ) break; else heapi = heapj; i = j; j = 2*j+1; heapi = temp; 59自下向上逐步調整為最小堆將一組用數(shù)組存放的任意數(shù)據(jù)調整成堆5317780923456587icurrentPos = i = 3012345675317780923456587currentPos = i = 2i0123456

30、7605317780923456587icurrentPos = i = 1012345675317780923456587i01234567615317780923456587icurrentPos = i = 00123456717780923456587i0901334567536217780923456587i17012345675317780923456587i012345675363堆的插入template int MinHeap : Insert ( const Type &x ) /在堆中插入新元素 x if ( CurrentSize = MaxHeapSize ) /堆滿

31、cerr 堆已滿 endl; return 0; heapCurrentSize = x; /插在最后 FilterUp (CurrentSize); /向上調整為堆 CurrentSize+; /堆計數(shù)增1 return 1;64最小堆的向上調整算法template void MinHeap : FilterUp ( int start ) /從 start 開始,向上直到0,調整堆 int j = start, i = (j-1)/2; / i 是 j 的雙親 Type temp = heapj; while ( j 0 ) if ( heapi = temp ) break; else

32、heapj = heapi; j = i; i = (i -1)/2; heapj = temp;6517780923456587i11在堆中插入新元素1153j最小堆的向上調整0123456785317780923456587j23i0123456781166177809456587j53i2317531178092345658723ji0123456781167最小堆的刪除算法template int MinHeap :Remove ( Type &x ) if ( !CurrentSize ) cout “ 堆已空 endl; return 0; x = heap0; /最小元素出隊列

33、heap0 = heapCurrentSize-1; /用最后元素 CurrentSize-; /填補 FilterDown ( 0, CurrentSize-1 ); /調整 return 1;68利用堆及其運算, 可以很容易地實現(xiàn)選擇排序的思路。堆排序分為兩個步驟 根據(jù)初始輸入數(shù)據(jù)，利用堆的調整算法 FilterDown( ) 形成初始堆; 通過一系列的對象交換和重新調整堆進行排序。堆排序 (Heap Sort)69建立初始的最大堆212525*491608012345i21 25 49 25* 16 08初始排序碼集合i212525*16490802543121 25 49 25* 16

34、 08i = 2 時的局部調整70i212525*49160801234521 25 49 25* 16 08i = 1 時的局部調整492525*16210802543149 25 21 25* 16 08i = 0 時的局部調整形成最大堆71基于初始堆進行堆排序最大堆堆頂V0具有最大的排序碼, 將V0與 Vn-1對調, 把具有最大排序碼的對象交換到最后, 再對前面的n-1個對象, 使用堆的調整算法FilterDown(0, n-2), 重新建立最大堆, 具有次最大排序碼的對象又上浮到V0位置。再對調V0和Vn-2,調用FilterDown(0, n-3), 對前n-2個對象重新調整，。如此

35、反復執(zhí)行，最后得到全部排序好的對象序列。這個算法即堆排序算法。72082525*16214902543108 25 21 25* 16 49交換 0 號與 5 號對象,5 號對象就位492525*21160801234549 25 21 25* 16 08初始最大堆731625*0825214902543116 25* 21 08 25 49交換 0 號與 4 號對象,4 號對象就位2525*0821164901234525 25* 21 08 16 49從 0 號到 4 號 重新調整為最大堆74081625*25214902543108 16 21 25* 25 49交換 0 號與 3 號對

36、象,3 號對象就位25*160821254901234525* 16 21 08 25 49從 0 號到 3 號 重新調整為最大堆753211625*08254901234521 16 08 25* 25 49從 0 號到 2 號 重新調整為最大堆081625*2521490254108 16 21 25* 25 49交換 0 號與 2 號對象,2 號對象就位76081625*25214902543108 16 21 25* 25 49交換 0 號與 1 號對象,1 號對象就位160825*21254901234516 08 21 25* 25 49從 0 號到 1 號 重新調整為最大堆77若

37、設堆中有 n 個結點, 且 2k-1 n 2k, 則對應的完全二叉樹有 k 層。在第 i 層上的結點數(shù) 2i (i = 0, 1, , k-1)。 在第一個形成初始堆的 for 循環(huán)中對每一個非葉結點調用了 一次堆調整算法FilterDown( ), 因此該循環(huán)所用的計算時間為：其中, i 是層序號, 2i 是第 i 層的最大結點數(shù), (k-i-1)是第 i 層結點能夠移動的最大距離。78第二個for循環(huán)中調用了n-1次FilterDown( )算法, 該循環(huán)的計算時間為O(nlog2n)。因此, 堆排序的時間復雜性為O(nlog2n)。該算法的附加存儲主要是在第二個for循環(huán)中用來執(zhí)行對象交

38、換時所用的一個臨時對象。因此，該算法的空間復雜性為O(1)。堆排序是一個不穩(wěn)定的排序方法。79歸并排序 (Merge Sort)歸并，是將兩個或兩個以上的有序表合并成一個新的有序表。例:對象序列initList中兩個有序表Vl Vm和Vm+1 Vn。它們可歸并成一個有序表, 存于另一對象序列mergedList的Vl Vn中。這種歸并方法稱為兩路歸并(2-way merging)。設變量 i 和 j 分別是表Vl Vm和Vm+1 Vn的當前檢測指針。變量 k 是存放指針。8008 21 25 25* 49 62 72 93 16 37 54 left mid mid+1 rightinitLi

39、sti j08 16 21 25 25* 37 49 54 62 72 93 left rightkmergeList當 i 和 j 都在兩個表的表長內變化時, 根據(jù)對應項的排序碼的大小, 依次把排序碼小的對象排放到新表 k 所指位置中；當 i 與 j 中有一個已經(jīng)超出表長時，將另一 個表中的剩余部分照抄到新表中。81迭代的歸并排序算法迭代的歸并排序算法就是利用兩路歸并過程進行排序的。其基本思想是：假設初始對象序列有 n 個對象，首先把它看成是 n 個長度為 1 的有序子序列 (歸并項)，先做兩兩歸并，得到 n / 2 個長度為 2 的歸并項 (如果 n 為奇數(shù)，則最后一個有序子序列的長度為1

40、)；再做兩兩歸并，如此重復，最后得到一個長度為 n 的有序序列。82迭代的歸并排序算法212525*9362720837165449len=1212525*4962930872163754len=2212525*4908627293len=416375408212525*49627293len=80816212525*374954627293len=1616375483在迭代的歸并排序算法中, 函數(shù)MergePass( ) 做一趟兩路歸并排序, 要調用merge ( )函數(shù) n/(2*len) O(n/len) 次, 函數(shù)MergeSort( )調用MergePass( )正好log2n 次,

41、而每次merge( )要執(zhí)行比較O(len)次, 所以算法總的時間復雜度為O(nlog2n)。歸并排序占用附加存儲較多, 需要另外一個與原待排序對象數(shù)組同樣大小的輔助數(shù)組。這是這個算法的缺點。歸并排序是一個穩(wěn)定的排序方法。84遞歸的表歸并排序與快速排序類似，歸并排序也可以利用劃分為子序列的方法遞歸實現(xiàn)。在遞歸的歸并排序方法中，首先要把整個待排序序列劃分為兩個長度大致相等的部分，分別稱之為左子表和右子表。對這些子表分別遞歸地進行排序，然后再把排好序的兩個子表進行歸并。圖示：待排序對象序列的排序碼為 21, 25, 49, 25*,16, 08 ，先是進行子表劃分，待到子表中只有一個對象時遞歸到底

42、。再是實施歸并，逐步退出遞歸調用的過程。8521 25 49 25* 16 08 21 25 49 25* 16 08 21 25 49 25 49 21 25* 16 08 25* 16 08 21 25 49 25* 16 08 16 08 25* 25 49 21 遞歸 21 25* 16 08 49 25 25* 16 08 21 25 49 回退86基數(shù)排序 (Radix Sort)基數(shù)排序是采用“分配”與“收集”的辦法，用對多排序碼進行排序的思想實現(xiàn)對單排序碼進行排序的方法。多排序碼排序以撲克牌排序為例。每張撲克牌有兩個“排序碼”：花色和面值。其有序關系為： 花色： 面值：2 3

43、4 5 6 7 8 9 10 J Q K A87如果我們把所有撲克牌排成以下次序： 2, , A, 2, , A, 2, , A, 2, , A這就是多排序碼排序。排序后形成的有序序列叫做詞典有序序列。對于上例兩排序碼的排序，可以先按花色排序，之后再按面值排序；也可以先按面值排序，再按花色排序。一般情況下，假定有一個 n 個對象的序列 V0, V1, , Vn-1 ，且每個對象Vi 中含有 d 個排序碼。88如果對于序列中任意兩個對象Vi 和Vj (0 i j n-1 ) 都滿足：則稱序列對排序碼 (K1, K2, , Kd) 有序。其中，K1 稱為最高位排序碼，Kd 稱為最低位排序碼。如果排

44、序碼是由多個數(shù)據(jù)項組成的數(shù)據(jù)項組，則依據(jù)它進行排序時就需要利用多排序碼排序。89實現(xiàn)多排序碼排序有兩種常用的方法最高位優(yōu)先MSD ( Most Significant Digit first )。最低位優(yōu)先LSD ( Least Significant Digit first)。90最高位優(yōu)先法通常是一個遞歸的過程：先根據(jù)最高位排序碼 K1排序, 得到若干對象組, 對象組中各對象都有相同排序碼K1。再分別對每組中對象根據(jù)排序碼 K2 進行排序, 按 K2 值的不同, 再分成若干個更小的子組, 每個子組中的對象具有相同的 K1和 K2值。依此重復, 直到對排序碼Kd完成排序為止。 最后, 把所有

45、子組中的對象依次連接起來，就得到一個有序的對象序列。91最低位優(yōu)先法首先依據(jù)最低位排序碼Kd對所有對象進行一趟排序，再依據(jù)次低位排序碼Kd-1對上一趟排序的結果再排序，依次重復，直到依據(jù)排序碼K1最后一趟排序完成，就可以得到一個有序的序列。使用這種排序方法對每一個排序碼進行排序時，不需要再分組，而是整個對象組都參加排序。LSD和MSD方法也可應用于對一個排序碼進行的排序。此時可將單排序碼 Ki 看作是一個子排序碼組：92基數(shù)排序是典型的LSD排序方法, 利用“分配”和“收集”對單排序碼進行排序。在這種方法中，把單排序碼 Ki 看成是一個d元組：其中的每一個分量 ( 1 j d ) 也可看成是一

46、個排序碼。鏈式基數(shù)排序93分量 (1 j d) 有radix種取值, 稱radix為基數(shù)。例如, 排序碼984可以看成是一個3元組(9, 8, 4), 每一位有 0, 1, , 9 等10種取值, 基數(shù)radix = 10。排序碼data可以看成是一個4元組(d, a, t, a), 每一位有a, b, , z等26種取值，radix = 26。針對d元組中的每一位分量, 把對象序列中的所有對象, 按 的取值，先“分配”到rd個隊列中去。然后再按各隊列的順序，依次把對象從隊列中“收集”起來，這樣所有對象按取值 排序完成。94如果對于所有對象的排序碼K0, K1, , Kn-1, 依次對各位的分

47、量, 讓 j = d, d-1, , 10, 分別用“分配”、“收集”的運算逐趟進行排序，在最后一趟“分配”、“收集” 完成后, 所有對象就按其排序碼的值從小到大排好序了。各隊列采用鏈式隊列結構, 分配到同一隊列的排序碼用鏈接指針鏈接起來。每一隊列設置兩 個隊列指針： int front radix指示隊頭， int rear radix 指向隊尾。為了有效地存儲和重排 n 個待排序對象，以靜態(tài)鏈表作為它們的存儲結構。95基數(shù)排序的“分配”與“收集”過程 第一趟614921485637738101215530790306第一趟分配（按最低位 i = 3 ）re0 re1 re2 re3 re4

48、 re5 re6 re7 re8 re9614738921485637101215530790306fr0 fr1 fr2 fr3 fr4 fr5 fr6 fr7 fr8 fr9第一趟收集53079092110161448521530663773896基數(shù)排序的“分配”與“收集”過程 第二趟614921485637738101215530790306第二趟分配（按次低位 i = 2 ）re0 re1 re2 re3 re4 re5 re6 re7 re8 re9614738921485637101215530790306fr0 fr1 fr2 fr3 fr4 fr5 fr6 fr7 fr8 f

49、r9第二趟收集53079092110161448521530663773897基數(shù)排序的“分配”與“收集”過程 第三趟614921485637738101215530790306第三趟分配（按最高位 i = 1 ）re0 re1 re2 re3 re4 re5 re6 re7 re8 re9614738921485637101215530790306fr0 fr1 fr2 fr3 fr4 fr5 fr6 fr7 fr8 fr9第三趟收集53079092110161448521530663773898各種排序方法的比較99外排序100 當待排序的對象數(shù)目特別多時，在內存中不能一次處理。必須把它們

50、以文件的形式存放于外存，排序時再把它們一部分一部分調入內存進行處理。這樣，在排序過程中必須不斷地在內存與外存之間傳送數(shù)據(jù)。這種基于外部存儲設備（或文件）的排序技術就是外排序。當對象以文件形式存放于磁盤上的時候, 通常是按物理塊存儲的。物理塊也叫做頁塊。每個頁塊可存放幾個對象。操作系統(tǒng)按頁塊對磁盤信息進行讀寫。磁盤通常是指由若干片磁盤組成的磁盤組, 各個盤片安裝在同一主軸上高速旋轉。各個盤面上半徑相同的磁道構成了柱面。各盤面設置一個讀寫磁頭，它們裝在同一動臂上，可以徑向從一個柱面移到另一個柱面上。外排序的基本過程101為了訪問某一頁塊, 先尋找柱面: 移動動臂使讀寫磁頭移到指定柱面上: 尋查(s

51、eek)。再根據(jù)磁道號(盤面號)選擇相應讀寫磁頭, 等待指定頁塊轉到讀寫磁頭下: 等待(latency)。 在磁盤組上存取一個頁塊的時間：102tiotseektlatencytrw基于磁盤進行的排序多使用歸并排序方法。其排序過程主要分為兩個階段： 建立用于外排序的內存緩沖區(qū)。根據(jù)它們的大小將輸入文件劃分為若干段, 用某種內排序方法對各段進行排序。經(jīng)過排序的段叫做初始歸并段或初始順串 (Run)。當它們生成后就被寫到外存中去。 仿照歸并樹模式, 把 生成的初始歸并段加以歸并, 一趟趟地擴大歸并段和減少歸并段個數(shù), 直到最后歸并成一個大歸并段(有序文件)為止。103示例：設有一個包含4500個對

52、象的輸入文件。現(xiàn)用一臺其內存至多可容納750個對象的計算機對該文件進行排序。輸入文件放在磁盤上,磁盤每個頁塊可容納250個對象, 這樣全部對象可存儲在 4500 / 25018 個頁塊中。輸出文件也放在磁盤上, 用以存放歸并結果。由于內存中可用于排序的存儲區(qū)域能容納750 個對象, 因此內存中恰好能存3個頁塊的對象。在外排序一開始, 把18塊對象, 每3塊一組, 讀入內存。利用某種內排序方法進行內排序, 形成初始歸并段, 再寫回外存?？偣部傻玫?個初始歸并段。然后一趟一趟進行歸并排序。104兩路歸并排序的歸并樹R1 750 R2 750 R3 750 R4 750 R5 750 R6 750初

53、始歸并段R12 1500 R34 1500 R56 1500R1234 3000R123456 4500第一趟歸并結果 第二趟歸并結果 第三趟歸并結果 105若把內存區(qū)域等份地分為 3 個緩沖區(qū)。其中的兩個為輸入緩沖區(qū), 一個為輸出緩沖區(qū), 可以在內存中利用簡單 2 路歸并函數(shù) merge( ) 實現(xiàn) 2 路歸并。首先, 從參加歸并排序的兩個輸入歸并段 R1 和 R2 中分別讀入一塊, 放在輸入緩沖區(qū)1 和輸入緩沖區(qū)2 中。然后在內存中進行 2 路歸并，歸并結果順序存放到輸出緩沖區(qū)中。106輸入緩沖區(qū) 2輸入緩沖區(qū) 1輸出緩沖區(qū)k路平衡歸并 (k-way Balanced merging)做

54、k 路平衡歸并時, 如果有 m 個初始歸并段, 則相應的歸并樹有 logkm +1 層, 需要歸并logkm 趟。下圖給出對有 36 個初始歸并段的文件做 6 路平衡歸并時的歸并樹。107做內部 k 路歸并時, 在 k 個對象中選擇最小者，需要順序比較 k-1 次。每趟歸并 n 個對象需要做(n-1)*(k-1)次比較, S 趟歸并總共需要的比較次數(shù)為: S*(n-1)*(k-1) = logkm * (n-1) * (k-1) = log2m * (n-1) * (k-1) / log2k 在初始歸并段個數(shù) m 與對象個數(shù) n 一定時, log2m*(n-1) = const, 而 (k-1

55、) / log2k 在 k 增大時趨于無窮大。因此, 增大歸并路數(shù) k, 會使得內部歸并的時間增大。108使用“敗者樹”從 k 個歸并段中選最小者, 當 k 較大時 (k 6)，選出排序碼最小的對象只需比較 log2k 次。 S*(n-1)*log2k = logkm * (n-1) * log2k = log2m * (n-1) * log2k / log2k = log2m * (n-1)排序碼比較次數(shù)與 k 無關, 總的內部歸并時間不會隨 k 的增大而增大。下面討論利用敗者樹在 k 個輸入歸并段中選擇最小者，實現(xiàn)歸并排序的方法。109 敗者樹是一棵完全二叉樹。其中 每個葉結點存放各歸并段

56、在歸并過程中當前參加比較的對象； 每個非葉結點記憶它兩個子女結點中對象排序碼小的結點(即敗者)；因此，根結點中記憶樹中當前對象排序碼最小的結點 (最小對象)。示例：設有 5 個初始歸并段, 它們中各對象的排序碼分別是：110 111Run0: 17, 21, Run1: 05, 44, Run2: 10, 12, Run3: 29, 32, Run4: 15, 56, 29321556172105441012151005172930241k3k4k0k1k2Run3Run4Run0Run1Run2ls1ls0ls2ls4ls3冠軍 (最小對象),輸出段1當前對象選中輸出段1最小對象，段1下一對

57、象參選，調整敗者樹11229321556172105441012151044172930142k3k4k0k1k2Run3Run4Run0Run1Run2ls1ls0ls2ls4ls3次最小對象選中初始歸并段的生成 (Run Generation)為減少讀寫磁盤次數(shù), 除增加歸并路數(shù) k 外, 還可減少初始歸并段個數(shù)m。在總對象數(shù)n 一定時, 要減少m, 必須增大初始歸并段長度。如果規(guī)定每個初始歸并段等長, 則此長度應根據(jù)生成它的內存工作區(qū)空間大小而定, 因而m的減少也就受到了限制。為了突破這個限制, 可采用敗者樹來生成初始歸并段。在使用同樣大內存工作區(qū)的情況下, 可以生成平均比原來等長情況下大一倍的初始歸并段, 從而減少初始歸并段個數(shù)。113設輸入文件FI中各對象的排序碼序列為 17, 21, 05, 44, 10, 12, 56, 32, 29 。選擇和置換過程的步驟如下： 從輸入文件FI中把 k 個對象讀入內存中, 并構造敗者樹。(內存中存放對象的數(shù)組r可容納的對象個數(shù)為 k )。 利用敗者樹在 r 中選擇一個