參考chap10排序

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

2、 80, 36, 14, 58, 61, 23, 97, 75,調(diào)整為,14, 23, 36, 49, 52, 58, 61 ,75, 80, 97,一般情況下，假設(shè)含n個記錄的序列為{ R1, R2, …， Rn }其相應(yīng)的關(guān)鍵字序列為 { K1, K2, …，Kn },這些關(guān)鍵字相互之間可以進行比較，即在它們之間存在著這樣一個關(guān)系 ： 　 Kp1≤Kp2≤…≤Kpn,按此固有關(guān)系將上式記錄序列重新

3、排列為 { Rp1, Rp2, …，Rpn }的操作稱作排序。,,二、內(nèi)部排序和外部排序,若整個排序過程不需要訪問外存便能完成，則稱此類排序問題為內(nèi)部排序；,反之，若參加排序的記錄數(shù)量很大， 整個序列的排序過程不可能在內(nèi)存中 完成，則稱此類排序問題為外部排序。,,三、內(nèi)部排序的方法,內(nèi)部排序的過程是一個逐步擴大記錄的有序序列長度的過程。,經(jīng)過一趟排序,有序序列區(qū),無 序 序 列 區(qū)

4、,有序序列區(qū),無 序 序 列 區(qū),,,,基于不同的“擴大” 有序序列長度的方法，內(nèi)部排序方法大致可分下列幾種類型：,插入類,交換類,選擇類,歸并類,其它方法,待排記錄的數(shù)據(jù)類型定義如下:,#define MAXSIZE 1000 // 待排順序表最大長度,typedef int KeyType; // 關(guān)鍵字類型為整數(shù)類型,typedef struct { KeyType key; // 關(guān)鍵

5、字項 InfoType otherinfo; // 其它數(shù)據(jù)項} RcdType; // 記錄類型,typedef struct { RcdType r[MAXSIZE+1]; // r[0]閑置 int length; // 順序表長度} SqList;

6、 // 順序表類型,,1. 插入類,將無序子序列中的一個或幾個記錄“插入”到有序序列中，從而增加記錄的有序子序列的長度。,,2. 交換類,通過“交換”無序序列中的記錄從而得到其中關(guān)鍵字最小或最大的記錄，并將它加入到有序子序列中，以此方法增加記錄的有序子序列的長度。,,3. 選擇類,從記錄的無序子序列中“選擇”關(guān)鍵字最小或最大的記錄，并將它加入到有序子序列中，以此方法增加記錄的有序子序列的長度。,,4. 歸并類,通過“歸并”兩個或

7、兩個以上的記錄有序子序列，逐步增加記錄有序序列的長度。,5. 其它方法,,10. 2 插 入 排 序,有序序列R[1..i-1],R[i],無序序列 R[i..n],一趟直接插入排序的基本思想：,有序序列R[1..i],無序序列 R[i+1..n],,,,實現(xiàn)“一趟插入排序”可分三步進行：,3．將R[i] 插入(復(fù)制)到R[j+1]的位置上。,2．將R[j+1..i-1]中的所有記錄均后移 一個位置；,1．在R[1.

8、.i-1]中查找R[i]的插入位置， R[1..j].key ? R[i].key < R[j+1..i-1].key；,直接插入排序（基于順序查找）,表插入排序（基于鏈表存儲）,不同的具體實現(xiàn)方法導(dǎo)致不同的算法描述,折半插入排序（基于折半查找）,希爾排序（基于逐趟縮小增量）,,一、直接插入排序,利用 “順序查找”實現(xiàn)“在R[1..i-1]中查找R[i]的插入位置”,算法的實現(xiàn)要點：,從R[i-1]起向前進行順序查找，

9、 監(jiān)視哨設(shè)置在R[0]；,R[0] = R[i]; // 設(shè)置“哨兵”,循環(huán)結(jié)束表明R[i]的插入位置為 j +1,,,R[0],,,j,,,,R[i],for (j=i-1; R[0].key<R[j].key; --j); // 從后往前找,j=i-1,插入位置,對于在查找過程中找到的那些關(guān)鍵字不小于R[i].key的記錄

10、，并在查找的同時實現(xiàn)記錄向后移動；,for (j=i-1; R[0].key<R[j].key; --j); R[j+1] = R[j],,,R[0],,,j,,,R[i],,,j= i-1,,上述循環(huán)結(jié)束后可以直接進行“插入”,插入位置,令 i = 2，3，…, n, 實現(xiàn)整個序列的排序。,for ( i=2; i<=n; ++i ) if (R[i].key<R[i-1].key)

11、 { 在 R[1..i-1]中查找R[i]的插入位置; 插入R[i] ; },void InsertionSort ( SqList &L ) { // 對順序表 L 作直接插入排序。 for ( i=2; i<=L.length; ++i ) if (L.r[i].key < L.r[i-1].key) { }} // Ins

12、ertSort,L.r[0] = L.r[i]; // 復(fù)制為監(jiān)視哨for ( j=i-1; L.r[0].key < L.r[j].key; -- j ) L.r[j+1] = L.r[j]; // 記錄后移L.r[j+1] = L.r[0]; // 插入到正確位置,內(nèi)部排序的時間分析：,實現(xiàn)內(nèi)部排序的基本操作有兩個：,（2）“移動”記錄。,（1）“比較”序列中兩個

13、關(guān)鍵字的 大??；,對于直接插入排序：,最好的情況（關(guān)鍵字在記錄序列中順序有序）：,“比較”的次數(shù)：,最壞的情況（關(guān)鍵字在記錄序列中逆序有序）：,“比較”的次數(shù)：,0,“移動”的次數(shù)：,“移動”的次數(shù)：,因為 R[1..i-1] 是一個按關(guān)鍵字有序的有序序列，則可以利用折半查找實現(xiàn)“在R[1..i-1]中查找R[i]的插入位置”，如此實現(xiàn)的插入排序為折半插入排序。,二、折半插入排序,void BiInsertionSo

14、rt ( SqList &L ) {} // BInsertSort,在 L.r[1..i-1]中折半查找插入位置；,for ( i=2; i<=L.length; ++i ) {} // for,L.r[0] = L.r[i]; // 將 L.r[i] 暫存到 L.r[0],for ( j=i-1; j>=high+1; --j ) L.r[j+1] = L.r[

15、j]; // 記錄后移,L.r[high+1] = L.r[0]; // 插入,low = 1; high = i-1;while (low<=high) { },m = (low+high)/2; // 折半,if (L.r[0].key < L.r[m].key) high = m-1; // 插入點在低半?yún)^(qū)else low = m+1; // 插入

16、點在高半?yún)^(qū),14 36 49 52 80,,,,,58 61 23 97 75,,,,,,i,,low,,high,,m,,,,m,,,low,low,,,m,,,high,,14 36 49 52 58 61 80,,,,,,,23 97 75,,,,i,,low,,high,,m,,high,,,m,,high,,,,m,,,low,,例如:,再如:,,插入位置,,插入位置,L.r,L.r,三、表插

17、入排序,為了減少在排序過程中進行的“移動”記錄的操作，必須改變排序過程中采用的存儲結(jié)構(gòu)。利用靜態(tài)鏈表進行排序，并在排序完成之后，一次性地調(diào)整各個記錄相互之間的位置，即將每個記錄都調(diào)整到它們所應(yīng)該在的位置上。,void LInsertionSort (Elem SL[ ]， int n){ // 對記錄序列SL[1..n]作表插入排序 SL[0].key = MAXINT ; SL[0].next = 1; SL

18、[1].next = 0; for ( i=2; i<=n; ++i ) for ( j=0, k = SL[0].next;SL[k].key<= SL[i].key ; j=k, k=SL[k].next ) { SL[j].next = i; SL[i].next = k; } // 結(jié)點i插入在結(jié)點j和結(jié)點k之間}// Linse

19、rtionSort,算法中使用了三個指針：其中：p指示第i個記錄的當(dāng)前位置 i指示第i個記錄應(yīng)在的位置 q指示第i+1個記錄的當(dāng)前位置,如何在排序之后調(diào)整記錄序列？,void Arrange ( Elem SL[ ], int n ) { p = SL[0].next; // p指示第一個記錄的當(dāng)前位置 for ( i=1; i<n; ++i ) {

20、 while (p<i) p = SL[p].next; q = SL[p].next; // q指示尚未調(diào)整的表尾 if ( p!= i ) { SL[p]←→SL[i]; // 交換記錄，使第i個記錄到位 SL[i].next = p; // 指向被移走的記錄 } p = q; // p指示尚未調(diào)整的表尾，

21、 // 為找第i+1個記錄作準(zhǔn)備 }} // Arrange,四、希爾排序（又稱縮小增量排序）,基本思想：對待排記錄序列先作“宏觀”調(diào)整，再作“微觀”調(diào)整。,所謂“宏觀”調(diào)整，指的是，“跳躍式”的插入排序。 具體做法為：,將記錄序列分成若干子序列，分別對每個子序列進行插入排序。,其中，d 稱為增量，它的值在排序過程中從大到小逐漸縮小，直至最后一趟排序減為 1。,例如：將 n 個記錄分成 d 個子序列： { R

22、[1]，R[1+d]，R[1+2d]，…，R[1+kd] } { R[2]，R[2+d]，R[2+2d]，…，R[2+kd] } … { R[d]，R[2d]，R[3d]，…，R[kd]，R[(k+1)d] },,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,例如：,16 25 12 30 47 11 23 36 9 18 31,第一趟希爾排序，設(shè)增量 d =5,11

23、 23 12 9 18 16 25 36 30 47 31,第二趟希爾排序，設(shè)增量 d = 3,9 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 ( SqList &L, int dk ) { for ( i=dk+1; i0&&(L

24、.r[0].key<L.r[j].key); j-=dk) L.r[j+dk] = L.r[j]; // 記錄后移，查找插入位置 L.r[j+dk] = L.r[0]; // 插入 } // if} // ShellInsert,void ShellSort (SqList &L, int dlta[], i

25、nt t){ // 增量為dlta[]的希爾排序 for (k=0; k<t; ++t) ShellInsert(L, dlta[k]); //一趟增量為dlta[k]的插入排序} // ShellSort,10.3 快 速 排 序,一、起泡排序,二、一趟快速排序,三、快速排序,四、快速排序的時間分析,,一、起泡排序,假設(shè)在排序過程中，記錄序列R[1..n]的

26、狀態(tài)為：,第 i 趟起泡排序,無序序列R[1..n-i+1],有序序列 R[n-i+2..n],,n-i+1,無序序列R[1..n-i],有序序列 R[n-i+1..n],,比較相鄰記錄，將關(guān)鍵字最大的記錄交換到 n-i+1 的位置上,,,,,,,,,,,void BubbleSort(Elem R[ ], int n) { while (i >1) { } /

27、/ while} // BubbleSort,i = n;,i = lastExchangeIndex; // 本趟進行過交換的 // 最后一個記錄的位置,if (R[j+1].key < R[j].key) { Swap(R[j], R[j+1]); lastExchangeIndex = j; //記下進行交換的記錄位置

28、 } //if,for (j = 1; j < i; j++),lastExchangeIndex = 1;,,注意:,2. 一般情況下，每經(jīng)過一趟“起泡”，“i 減一”，但并不是每趟都如此。,例如:,2,5,5,3,1,5,7,9,8,9,,i=7,,i=6,for (j = 1; j < i; j++) if (R[j+1].key < R[j].key) …,,1,3,,i=2,,1. 起

29、泡排序的結(jié)束條件為， 最后一趟沒有進行“交換記錄”。,,時間分析:,最好的情況（關(guān)鍵字在記錄序列中順序有序）： 只需進行一趟起泡,“比較”的次數(shù)：,最壞的情況（關(guān)鍵字在記錄序列中逆序有序）： 需進行n-1趟起泡,“比較”的次數(shù)：,0,“移動”的次數(shù)：,“移動”的次數(shù)：,n-1,,二、一趟快速排序（一次劃分）,目標(biāo)：找一個記錄，以它的關(guān)鍵字作為“樞軸”，凡其關(guān)鍵字小于樞軸的記錄均移動至該記錄之前，反之，凡

30、關(guān)鍵字大于樞軸的記錄均移動至該記錄之后。,致使一趟排序之后，記錄的無序序列R[s..t]將分割成兩部分：R[s..i-1]和R[i+1..t]，且 R[j].key≤ R[i].key ≤ R[j].key (s≤j≤i-1) 樞軸 (i+1≤j≤t)。,,,s,t,,low,,high,設(shè) R[s]=52 為樞軸,將 R[high].key 和 樞軸的關(guān)鍵字進行比較，要求R[high].ke

31、y ≥ 樞軸的關(guān)鍵字,將 R[low].key 和 樞軸的關(guān)鍵字進行比較，要求R[low].key ≤ 樞軸的關(guān)鍵字,,high,,23,,low,,80,,high,,14,,low,,52,例如,R[0],52,,low,,high,,high,,high,,low,可見，經(jīng)過“一次劃分” ，將關(guān)鍵字序列 52, 49, 80, 36, 14, 58, 61, 97, 23, 75 調(diào)整為: 2

32、3, 49, 14, 36, (52) 58, 61, 97, 80, 75,,在調(diào)整過程中，設(shè)立了兩個指針： low 和high，它們的初值分別為： s 和 t，,之后逐漸減小 high，增加 low，并保證 R[high].key≥52，和 R[low].key≤52,否則進行記錄的“交換”。,int Partition (RedType& R[], int low, int high) { pivotke

33、y = R[low].key; while (low=pivotkey) --high; R[low]←→R[high]; while (low<high && R[low].key<=pivotkey) ++low; R[low]←→R[high]; } return low; // 返回樞軸所在位置} //

34、 Partition,int Partition (RedType R[], int low, int high) {}// Partition,R[0] = R[low]; pivotkey = R[low].key; // 樞軸,while (low<high) {},while(low=pivotkey) -- high; // 從右向左搜索,R[low] =

35、 R[high];,while (low<high && R[low].key<=pivotkey) ++ low; // 從左向右搜索,R[high] = R[low];,R[low] = R[0]; return low;,,三、快速排序,首先對無序的記錄序列進行“一次劃分”，之后分別對分割所得兩個子序列“遞歸”進行快速排序。,無 序 的 記 錄 序 列,無序記錄子序列

36、(1),無序子序列(2),樞軸,,一次劃分,,,分別進行快速排序,void QSort (RedType & R[], int s, int t ) { // 對記錄序列R[s..t]進行快速排序 if (s < t-1) { // 長度大于1 }} // QSort,pivotloc = Partition(R, s, t);

37、 // 對 R[s..t] 進行一次劃分,QSort(R, s, pivotloc-1); // 對低子序列遞歸排序，pivotloc是樞軸位置,QSort(R, pivotloc+1, t); // 對高子序列遞歸排序,void QuickSort( SqList & L) { // 對順序表進行快速排序 QSort(L.r, 1, L.length);} // QuickSort,

38、第一次調(diào)用函數(shù) Qsort 時，待排序記錄序列的上、下界分別為 1 和 L.length。,,四、快速排序的時間分析,假設(shè)一次劃分所得樞軸位置 i=k，則對n 個記錄進行快排所需時間：,其中 Tpass(n)為對 n 個記錄進行一次劃分所需時間。,若待排序列中記錄的關(guān)鍵字是隨機分布的，則 k 取 1 至 n 中任意一值的可能性相同。,T(n) = Tpass(n) + T(k-1) + T(n-k),設(shè) Tavg(1)≤b,則可得結(jié)果：

39、,結(jié)論: 快速排序的時間復(fù)雜度為O(nlogn),由此可得快速排序所需時間的平均值為：,若待排記錄的初始狀態(tài)為按關(guān)鍵字有序時，快速排序?qū)⑼懟癁槠鹋菖判?，其時間復(fù)雜度為O(n2)。,為避免出現(xiàn)這種情況，需在進行一次劃分之前，進行“予處理”，即：,先對 R(s).key, R(t).key 和 R[?(s+t)/2?].key，進行相互比較，然后取關(guān)鍵字為 “三者之中”的記錄為樞軸記錄。,,10.4 堆 排 序,簡 單 選

40、擇 排 序,堆 排 序,,一、簡單選擇排序,假設(shè)排序過程中，待排記錄序列的狀態(tài)為：,有序序列R[1..i-1],無序序列 R[i..n],第 i 趟簡單選擇排序,從中選出關(guān)鍵字最小的記錄,,有序序列R[1..i],無序序列 R[i+1..n],,,簡單選擇排序的算法描述如下：,void SelectSort (Elem R[], int n ) { // 對記錄序列R[1..n]作簡單選擇排序。 for (i=1; i&l

41、t;n; ++i) { // 選擇第 i 小的記錄，并交換到位 }} // SelectSort,j = SelectMinKey(R, i); // 在 R[i..n] 中選擇關(guān)鍵字最小的記錄,if (i!=j) R[i]←→R[j]; // 與第 i 個記錄交換,時間性能分析,對 n 個記錄進行簡單選擇排序，所需進行的

42、 關(guān)鍵字間的比較次數(shù) 總計為：,移動記錄的次數(shù)，最小值為 0, 最大值為3(n-1) 。,,二、堆排序,堆是滿足下列性質(zhì)的數(shù)列{r1, r2, …，rn}：,或,堆的定義:,{12, 36, 27, 65, 40, 34, 98, 81, 73, 55, 49},例如:,是小頂堆,{12, 36, 27, 65, 40, 14, 98, 81, 73, 55, 49},不是堆,(小頂堆),(大頂堆),ri,r2i,r2i+1,,,若將該

43、數(shù)列視作完全二叉樹，則 r2i 是 ri 的左孩子； r2i+1 是 ri 的右孩子。,12,36,27,65,49,81,73,55,40,34,98,,,,,,,,,,,例如:,是堆,14,不,堆排序即是利用堆的特性對記錄序列進行排序的一種排序方法。,例如：,,建大頂堆,{ 98, 81, 49, 73, 36, 27, 40, 55, 64, 12 },,{ 12, 81, 49, 73, 36, 27, 40, 55, 64,

44、 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 },經(jīng)過篩選,void HeapSort ( HeapType &H ) { // 對順序表 H 進行堆排序} // HeapSort,for ( i=H.length/2; i>

45、;0; --i ) HeapAdjust ( H.r, i, H.length ); // 建大頂堆,for ( i=H.length; i>1; --i ) { H.r[1]←→H.r[i]; // 將堆頂記錄和當(dāng)前未經(jīng)排序子序列 // H.r[1..i]中最后一個記錄相互交換 HeapAdjust(H.r, 1, i-1);

46、 // 對 H.r[1] 進行篩選},,如何“建堆”？,兩個問題:,如何“篩選”？,定義堆類型為:,typedef SqList HeapType; // 堆采用順序表表示之,,所謂“篩選”指的是，對一棵左/右子樹均為堆的完全二叉樹，“調(diào)整”根結(jié)點使整個二叉樹也成為一個堆。,,,,,,,,,,,,堆,堆,,篩選,98,81,49,73,55,64,12,36,27,40,,,,

47、,,,,,,例如:,是大頂堆,12,但在 98 和 12 進行互換之后，它就不是堆了，,因此，需要對它進行“篩選”。,98,,,,12,81,,,73,,,,,64,12,,98,比較,比較,,,void HeapAdjust (RcdType &R[], int s, int m){ // 已知 R[s..m]中記錄的關(guān)鍵字除 R[s] 之外均 // 滿足堆的特征，本函數(shù)自上而下調(diào)整 R[s] 的 //

48、關(guān)鍵字，使 R[s..m] 也成為一個大頂堆} // HeapAdjust,rc = R[s]; // 暫存 R[s],for ( j=2*s; j<=m; j*=2 ) { // j 初值指向左孩子 自上而下的篩選過程;},R[s] = rc; // 將調(diào)整前的堆頂記錄插入到 s 位置,,if ( rc.key >= R[j].key ) break; // 再作“

49、根”和“子樹根”之間的比較， // 若“>=”成立，則說明已找到 rc 的插 // 入位置 s ，不需要繼續(xù)往下調(diào)整,R[s] = R[j]; s = j; // 否則記錄上移，尚需繼續(xù)往下調(diào)整,if ( j<m && R[j].key<R[j+1].key ) ++j; // 左/右“子樹根”

50、之間先進行相互比較 // 令 j 指示關(guān)鍵字較大記錄的位置,,建堆是一個從下往上進行“篩選”的過程。,40,55,49,73,81,64,36,12,27,98,,,,,,,,,,例如: 排序之前的關(guān)鍵字序列為,,12,36,,81,73,,49,98,,81,73,55,現(xiàn)在，左/右子樹都已經(jīng)調(diào)整為堆，最后只要調(diào)整根結(jié)點，使整個二叉樹是個“堆”即可。,98,49,40,64,36,12,27,,堆排序的時間復(fù)

51、雜度分析：,1. 對深度為 k 的堆，“篩選”所需進行的關(guān)鍵字比較的次數(shù)至多為2(k-1)；,3. 調(diào)整“堆頂” n-1 次，總共進行的關(guān)鍵 字比較的次數(shù)不超過 2 (?log2(n-1)?+ ?log2(n-2)?+ …+log22) < 2n(?log2n?),因此，堆排序的時間復(fù)雜度為O(nlogn)。,,2. 對 n 個關(guān)鍵字，建成深度為h(=?log2n?+1)的堆，所需進行的關(guān)鍵字比較的次數(shù)至多 4n；,

52、10.5 歸 并 排 序,歸并排序的過程基于下列基本思想進行： 將兩個或兩個以上的有序子序列 “歸并” 為一個有序序列。,在內(nèi)部排序中，通常采用的是2-路歸并排序。即：將兩個位置相鄰的記錄有序子序列,歸并為一個記錄的有序序列。,有 序 序 列 R[l..n],有序子序列 R[l..m],有序子序列 R[m+1..n],這個操作對順序表而言，是輕而易舉的。,void Merge (RcdType SR[], RcdType

53、&TR[], int i, int m, int n) { // 將有序的記錄序列 SR[i..m] 和 SR[m+1..n] // 歸并為有序的記錄序列 TR[i..n]} // Merge,for (j=m+1, k=i; i<=m && j<=n; ++k)

54、 { // 將SR中記錄由小到大地并入TR if (SR[i].key<=SR[j].key) TR[k] = SR[i++]; else TR[k] = SR[j++]; },… …,,if (i<=m) TR[k..n] = SR[i..m]; // 將剩余的 SR[i..m] 復(fù)制到 TR,if (j<=n) TR

55、[k..n] = SR[j..n]; // 將剩余的 SR[j..n] 復(fù)制到 TR,,歸并排序的算法,如果記錄無序序列 R[s..t] 的兩部分 R[s..?(s+t)/2?] 和 R[?(s+t)/2?+1..t]分別按關(guān)鍵字有序，則利用上述歸并算法很容易將它們歸并成整個記錄序列是一個有序序列。,由此，應(yīng)該先分別對這兩部分進行 2-路歸并排序。,例如：,52,

56、23, 80, 36, 68, 14 (s=1, t=6),[ 52, 23, 80] [36, 68, 14],[ 52, 23][80],[ 52],[ 23, 52],[ 23, 52, 80],[36, 68][14],[36][68],[36, 68],[14, 36, 68],[ 14, 23, 36, 52, 68, 80 ],[23],,,,,,,,,,,voi

57、d Msort ( RcdType SR[], RcdType &TR1[], int s, int t ) { // 將SR[s..t] 歸并排序為 TR1[s..t] if (s= =t) TR1[s]=SR[s]; else { }} // Msort,… …,,m = (s+t)/2; //

58、 將SR[s..t]平分為SR[s..m]和SR[m+1..t],Msort (SR, TR2, s, m); // 遞歸地將SR[s..m]歸并為有序的TR2[s..m]Msort (SR, TR2, m+1, t); //遞歸地SR[m+1..t]歸并為有序的TR2[m+1..t],Merge (TR2, TR1, s, m, t); // 將TR2[s..m]和TR2[m+1..t]歸并到TR

59、1[s..t],,void MergeSort (SqList &L) { // 對順序表 L 作2-路歸并排序 MSort(L.r, L.r, 1, L.length);} // MergeSort,容易看出，對 n 個記錄進行歸并排序的時間復(fù)雜度為Ο(nlogn)。即： 每一趟歸并的時間復(fù)雜度為 O(n)， 總共需進行 ?log2n? 趟。,,10.6 基 數(shù) 排 序,基數(shù)排序是一種借助“多

60、關(guān)鍵字排序”的思想來實現(xiàn)“單關(guān)鍵字排序”的內(nèi)部排序算法。,多關(guān)鍵字的排序,鏈?zhǔn)交鶖?shù)排序,,一、多關(guān)鍵字的排序,n 個記錄的序列 { R1, R2, …，Rn}對關(guān)鍵字 (Ki0, Ki1,…,Kid-1) 有序是指：,其中: K0 被稱為 “最主”位關(guān)鍵字,Kd-1 被稱為 “最次”位關(guān)鍵字,對于序列中任意兩個記錄 Ri 和 Rj(1≤i<j≤n) 都滿足下列(詞典)有序關(guān)系： (Ki0, Ki1, …,Kid

61、-1) < (Kj0, Kj1, …,Kjd-1),實現(xiàn)多關(guān)鍵字排序通常有兩種作法:,最低位優(yōu)先LSD法,最高位優(yōu)先MSD法,,先對K0進行排序，并按 K0 的不同值將記錄序列分成若干子序列之后，分別對 K1 進行排序，...…， 依次類推，直至最后對最次位關(guān)鍵字排序完成為止。,,先對 Kd-1 進行排序，然后對 Kd-2 進行排序，依次類推，直至對最主位關(guān)鍵字 K0 排序完成為止。,排序過程中不需要根據(jù) “前一個” 關(guān)鍵

62、字的排序結(jié)果，將記錄序列分割成若干個(“前一個”關(guān)鍵字不同的)子序列。,例如:學(xué)生記錄含三個關(guān)鍵字:系別、班號和班內(nèi)的序列號，其中以系別為最主位關(guān)鍵字。,,,,,,,,,,無序序列,對K2排序,對K1排序,對K0排序,3,2,30,1,2,15,3,1,20,2,3,18,2,1,20,1,2,15,2,3,18,3,1,20,2,1,20,3,2,30,3,1,20,2,1,20,1,2,15,3,2,30,2,3,18,1,2,1

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

64、, 185, 247, 606, 230, 834, 539 },首先按其 “個位數(shù)” 取值分別為 0, 1, …, 9　 “分配” 成 10 組，之后按從 0 至 9 的順序?qū)?它們 “收集” 在一起；,然后按其 “十位數(shù)” 取值分別為 0, 1, …, 9 “分配” 成 10 組，之后再按從 0 至 9 的順序?qū)⑺鼈?“收集” 在一起；,最后按其“百位數(shù)”重復(fù)一遍上述操作。,在計算機上實現(xiàn)基數(shù)排序時，為減

65、少所需輔助存儲空間，應(yīng)采用鏈表作存儲結(jié)構(gòu)，即鏈?zhǔn)交鶖?shù)排序，具體作法為：,１．待排序記錄以指針相鏈，構(gòu)成一個鏈表；,２．“分配” 時，按當(dāng)前“關(guān)鍵字位”所取值，將記錄分配到不同的 “鏈隊列” 中，每個隊列中記錄的 “關(guān)鍵字位” 相同；,３．“收集”時，按當(dāng)前關(guān)鍵字位取值從小到大將各隊列首尾相鏈成一個鏈表;,４．對每個關(guān)鍵字位均重復(fù) 2) 和 3) 兩步。,例如：,p→369→367→167→239→237→138→230→139,進行第一

66、次分配,進行第一次收集,f[0] r[0],f[7] r[7],f[8] r[8],f[9] r[9],p→230,→230←,→367 ←,→167,→237,→367→167→237,→138,→368→239→1

67、39,→369 ←,→239,→139,→138←,進行第二次分配,p→230→237→138→239→139,p→230→367→167→237→138→368→239→139,f[3] r[3],f[6] r[6],→230

68、 ←,→237,→138,→239,→139,→367 ←,→167,→368,→367→167→368,進行第二次收集,進行第三次收集之后便得到記錄的有序序列,f[1] r[1],p→230→237→138→239→139→367→167→368,進行第三次

69、分配,f[2] r[2],f[3] r[3],→138 ←,→139,→167,→230 ←,→237,→239,→367 ←,→368,p→138→139→167,→230→237→239,→367→368,提醒注意：,１．“分配”