第十章內(nèi)部排序

1、1第十章第十章 內(nèi)部排序內(nèi)部排序 排序排序(sort):(sort):將一組數(shù)據(jù)元素任意的序列，重新排列成一組按將一組數(shù)據(jù)元素任意的序列，重新排列成一組按 關(guān)鍵字有序的序列。關(guān)鍵字有序的序列。 穩(wěn)定與不穩(wěn)定：穩(wěn)定與不穩(wěn)定：一種排序方法，如果排序后具有相同關(guān)鍵字的一種排序方法，如果排序后具有相同關(guān)鍵字的 記錄仍維持排序之前的相對次序，則稱之為記錄仍維持排序之前的相對次序，則稱之為穩(wěn)定穩(wěn)定 的，否則稱為的，否則稱為不穩(wěn)定不穩(wěn)定的。的。 例如：例如： 排序前為：排序前為： 4949，3838，6565，9797，7676，1313，2727，4949 排序后為：排序后為： 1313，2727，383

2、8，4949，4949，6565，7676，97 97 該排序是穩(wěn)定的該排序是穩(wěn)定的 1313，2727，3838，4949，4949，6565，7676，97 97 該排序是不穩(wěn)定的該排序是不穩(wěn)定的2內(nèi)部排序：內(nèi)部排序：待排序的數(shù)據(jù)若存儲在內(nèi)存中，在內(nèi)待排序的數(shù)據(jù)若存儲在內(nèi)存中，在內(nèi)存中加以處理的，這種排序方法叫內(nèi)部排序。存中加以處理的，這種排序方法叫內(nèi)部排序。外部排序：外部排序：如果在排序過程中，數(shù)據(jù)的主要部分如果在排序過程中，數(shù)據(jù)的主要部分存放在外存儲器中（如軟盤、硬盤、磁帶），借存放在外存儲器中（如軟盤、硬盤、磁帶），借助內(nèi)存進行內(nèi)、外存數(shù)據(jù)交換，逐步排列記錄之助內(nèi)存進行內(nèi)、外存數(shù)據(jù)交

3、換，逐步排列記錄之間的順序，則稱之為外部排序。間的順序，則稱之為外部排序。內(nèi)部排序可分五類：內(nèi)部排序可分五類：插入排序、交換排序、選擇插入排序、交換排序、選擇排序、歸并排序和計數(shù)（分配）排序。排序、歸并排序和計數(shù)（分配）排序。10.1 概概 述述3待排序記錄的存儲方式：待排序記錄的存儲方式：1）地址連續(xù)的一組存儲單元（順序存儲），排序時需移動記錄）地址連續(xù)的一組存儲單元（順序存儲），排序時需移動記錄2）靜態(tài)鏈表，排序時不需移動記錄，僅需修改指針）靜態(tài)鏈表，排序時不需移動記錄，僅需修改指針3）記錄存放在地址連續(xù)的一組存儲單元中，再設(shè)一組地址向量，排）記錄存放在地址連續(xù)的一組存儲單元中，再設(shè)一組地

4、址向量，排序時不需移動記錄，結(jié)束后再調(diào)整記錄的存儲位置。序時不需移動記錄，結(jié)束后再調(diào)整記錄的存儲位置。待排記錄的數(shù)據(jù)類型：待排記錄的數(shù)據(jù)類型： （以第一種方式討論）（以第一種方式討論）#define MAXSIZE 20 typedef int KeyType ; typedef struct KeyType key; InfoType otherinfo; RedType; /記錄類型記錄類型 typedef struct RedType rMAXSIZE+1; /r0閑置或作崗哨閑置或作崗哨 int length; SqList; /表的類型表的類型10.1 概概 述述410.2 插入排序

5、插入排序10.2.1 直接插入排序直接插入排序 直接插入排序：直接插入排序：將一個記錄插入到已排好序的有序表中，將一個記錄插入到已排好序的有序表中，從而得到一個新的、記錄數(shù)增一的有序表。從而得到一個新的、記錄數(shù)增一的有序表。 void Insertsort(Sqlist &L) for (i=2; i=L.length; +i) if (LT(L.ri.key, L.ri-1.key) /需將需將L.ri-1插入到有序子表插入到有序子表 L.r0=L.ri; /將將L.ri復(fù)制到崗哨復(fù)制到崗哨 L.ri=L.ri-1; for(j=i-2; LT(L.r0.key,L.rj.key);

6、 -j ) L.rj+1=L.rj; /記錄后移記錄后移 L.rj+1=L.r0; /插入到正確位置插入到正確位置 時間復(fù)雜度？時間復(fù)雜度？510.2.2 其他插入排序其他插入排序1.折半插入排序折半插入排序 上述插入排序的基本操作是在一個有序表中進行查找和插入，查上述插入排序的基本操作是在一個有序表中進行查找和插入，查找可以用折半查找來實現(xiàn)，稱之為折半插入排序。找可以用折半查找來實現(xiàn)，稱之為折半插入排序。 void BInsertsort(Sqlist &L) for (i=2;i=L.length;+i) L.r0=L.ri; low=1; high=i-1; while (low

7、=high+1;-j ) L.rj+1=L.rj; L.rhigh+1=L.r0; 折半插入排序僅減少了關(guān)鍵字的比較次數(shù)，而沒有減少移動次數(shù)。折半插入排序僅減少了關(guān)鍵字的比較次數(shù)，而沒有減少移動次數(shù)。時間復(fù)雜度仍為時間復(fù)雜度仍為O( n2 )6 2路插入排序路插入排序 2路插入排序是在折半插入排序的基礎(chǔ)上再改進之，其目路插入排序是在折半插入排序的基礎(chǔ)上再改進之，其目的是減少排序過程中記錄的移動次數(shù)，但需要的是減少排序過程中記錄的移動次數(shù)，但需要n個記錄的個記錄的輔助空間。輔助空間。 具體方法具體方法：另設(shè)一個和：另設(shè)一個和L.r同類型的數(shù)組同類型的數(shù)組d，首先將，首先將L.r1賦值給賦值給d1

8、，并將，并將d1看成是在排好序的序列中處于中間看成是在排好序的序列中處于中間位置的記錄，然后從位置的記錄，然后從L.r中第二個記錄起依次插入到中第二個記錄起依次插入到d1之之前或之后的有序序列中。先將待插記錄的關(guān)鍵字和前或之后的有序序列中。先將待插記錄的關(guān)鍵字和d1的的關(guān)鍵字進行比較，若關(guān)鍵字進行比較，若L.ri.keyi的分量，則互換的分量，則互換SL.ri和和SL.rp，且令，且令SL.ri中指針域的中指針域的值改為值改為p，由于此時數(shù)組中所有小于，由于此時數(shù)組中所有小于i的分量中已是的分量中已是“到位到位”的記錄，則當?shù)挠涗?，則當p=i為止。為止。 void Arrange(SLinkL

9、istType &SL) p=SL.r0.next; for (i=1;iSL.length;+i) while (pi) p=SL.rp.next; q=SL.rp.next; if (p!=i) SL.rpSL.ri; SL.ri.next=p; p=q; 表插入排表插入排序序910.2.3 希爾排序希爾排序 希爾排序希爾排序（shells method) shells method) 又稱又稱“縮小增量排序縮小增量排序”。 基本思想：基本思想：先將整個待排記錄序列分割成若干子序列先將整個待排記錄序列分割成若干子序列, ,在每個子序列內(nèi)分別進行直接插入排序，待整個序列在每個子序列內(nèi)

10、分別進行直接插入排序，待整個序列中的記錄基本有序時，再對全體記錄進行一次直接插中的記錄基本有序時，再對全體記錄進行一次直接插入排序。入排序。 注意注意: :子序列的劃分不是簡單地子序列的劃分不是簡單地“逐段分割逐段分割”, ,而是將相而是將相距某個距某個“增量增量”的記錄組成一個子序列。的記錄組成一個子序列?！霸隽吭隽俊币灰淮伪纫淮涡?，直到增量為次比一次小，直到增量為1 1。10 void ShellInsert(SqList &L, int dk) /對對L作一趟希爾插入排序，作一趟希爾插入排序，dk為增量為增量 for (i=dk+1; i0&LT(L.r0.key,L.r

11、j.key) ; j=j-dk) L.rj+dk=L.rj; L.rj+dk=L.r0; Void ShellSort(SqList &L, int dlta, int t) /增量序列增量序列dlta0.t-1 for (k=0; kt; +k) ShellInsert(L, dltak); 10.2.3 希爾排序希爾排序1110. 3 交換排序交換排序 借助借助“交換交換”進行的排序進行的排序 主要包括：主要包括：起泡排序和快速排序。起泡排序和快速排序。 起泡排序起泡排序：首先將第一個記錄的關(guān)鍵字和第二個記錄：首先將第一個記錄的關(guān)鍵字和第二個記錄的關(guān)鍵字進行比較，若為逆序，則將兩個

12、記錄交換之，的關(guān)鍵字進行比較，若為逆序，則將兩個記錄交換之，然后比較地二個記錄和第三個記錄的關(guān)鍵字，依次類然后比較地二個記錄和第三個記錄的關(guān)鍵字，依次類推，直至第推，直至第n-1個記錄和第個記錄和第n記錄的關(guān)鍵字進行過比較記錄的關(guān)鍵字進行過比較為止。上述過程稱第一趟氣泡排序，其結(jié)果時最大的為止。上述過程稱第一趟氣泡排序，其結(jié)果時最大的記錄被放到了最后的位置上。然后再進行第二趟、第記錄被放到了最后的位置上。然后再進行第二趟、第三趟三趟 時間復(fù)雜度：時間復(fù)雜度：O( n2 )12 快速排序（快速排序（Quick Sort）基本思想）基本思想：通過一趟排序?qū)⒋和ㄟ^一趟排序?qū)⒋庞涗浄指畛瑟毩⒌膬刹?/p>

13、分，其中一部分記錄的關(guān)鍵字均比排記錄分割成獨立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，然后再分別對這兩部分記錄繼續(xù)另一部分記錄的關(guān)鍵字小，然后再分別對這兩部分記錄繼續(xù)進行排序，以達到整個序列有序。進行排序，以達到整個序列有序。 選取一記錄作為選取一記錄作為樞軸樞軸（pivot） （一般為第一個記錄）（一般為第一個記錄）,將待排記錄分成兩部分。比樞軸小的放在其前面，反之放在將待排記錄分成兩部分。比樞軸小的放在其前面，反之放在其后面。其后面。 一趟快速排序一趟快速排序的具體做法：附設(shè)兩個指針的具體做法：附設(shè)兩個指針i和和j，它們的，它們的初值分別為初值分別為low和和high，

14、設(shè)樞軸記錄的關(guān)鍵字為，設(shè)樞軸記錄的關(guān)鍵字為pivotkey，則首先從則首先從j所指位置起向前搜索找到第一個關(guān)鍵字小于所指位置起向前搜索找到第一個關(guān)鍵字小于pivotkey的記錄移到的記錄移到i的位置上，然后從的位置上，然后從i所指位置起向后搜索，所指位置起向后搜索，找到第一個關(guān)鍵字大于找到第一個關(guān)鍵字大于pivotkey的記錄移到的記錄移到j(luò)的位置上，重復(fù)的位置上，重復(fù)這兩步直到這兩步直到i=j為止。為止。10. 3 交換排序交換排序-快速排序快速排序13 int Partition(SqList &L, int low, int high) /一趟快速排序一趟快速排序 i=low;

15、j=high; L.r0=L.ri; pivotkey=L.ri.key; while (ij) while (i=pivotkey) -j; L.ri=L.rj; /比樞軸記錄小的記錄移到底端比樞軸記錄小的記錄移到底端 while (ij & L.ri.key=pivotkey) +i; L.rj=L.ri; /比樞軸記錄大的記錄移到高端比樞軸記錄大的記錄移到高端 L.ri=L.r0; return i; /返回返回樞軸樞軸的位置的位置 10. 3 交換排序交換排序-快速排序的算法快速排序的算法14 void Qsort(SqList &L, int low, int hig

16、h) /對順序表對順序表L中的子序列中的子序列L.rlow.high 作快速排序作快速排序 if (lowhigh)/長度大于長度大于 pivotloc=Partition(L,low,high); Qsort(L,low,pivotloc-1); Qsort(L,pivotloc+1,high); void QuickSort(SqList &L) /對順序表對順序表L作快速排序作快速排序 Qsort(L, 1, L.length); 10. 3 交換排序交換排序-快速排序的算法快速排序的算法1510.4 選擇排序選擇排序 選擇排序：選擇排序：每一趟在每一趟在n-i+1(i=1,2,

17、3,n-1)個記錄中選擇關(guān)鍵個記錄中選擇關(guān)鍵字最小的記錄作為有序序列中第字最小的記錄作為有序序列中第i個記錄。個記錄。 10.4.1 簡單選擇排序簡單選擇排序 一趟簡單選擇排序一趟簡單選擇排序：通過通過n-i次關(guān)鍵字間的比較，從次關(guān)鍵字間的比較，從n-i+1個記個記錄中選出關(guān)鍵字最小的記錄，并和第錄中選出關(guān)鍵字最小的記錄，并和第i個記錄交換之。個記錄交換之。 void SelectSort(SqList &L) /對順序表作簡單選擇排序?qū)樞虮碜骱唵芜x擇排序 for (i=1; iL.length; +i) j=SelectMinKey(L,i);/在在L.ri.L.length中選最

18、小的記錄中選最小的記錄,位置位置為為j if (i!=j) L.riL.rj; /兩記錄交換兩記錄交換 16舉例：舉例： 30,26,28,35,47,18,32,16,45,37 第一趟第一趟: 16,26,28,35,47,18,32,30,45,37 /j=8,L.r1L.r8第二趟第二趟: 16,18,28,35,47,26,32,30,45,37 /j=6,L.r2L.r6第三趟第三趟: 16,18,26,35,47,28,32,30,45,37 /j=6,L.r3L.r6第四趟第四趟: 16,18,26,28,47,35,32,30,45,37 /j=6,L.r4L.r6第五趟第五

19、趟: 16,18,26,28,30,35,32,47,45,37 /j=8,L.r5L.r8第六趟第六趟: 16,18,26,28,30,32,35,47,45,37 /j=7,L.r6L.r7第七趟第七趟: 16,18,26,28,30,32,35,47,45,37 /j=7,不需交換不需交換第八趟第八趟: 16,18,26,28,30,32,35,37,45,47 /j=10,L.r8L.r10第九趟第九趟: 16,18,26,28,30,32,35,37,45,47 /j=9,不需交換不需交換1710.4.2 樹形選擇排序樹形選擇排序 樹形選擇排序又稱錦標賽排序樹形選擇排序又稱錦標賽排序

20、，首先對，首先對n個個記錄的關(guān)鍵字進行兩兩比較，然后在其中記錄的關(guān)鍵字進行兩兩比較，然后在其中 n/2 個個較小者之間再進行兩兩比較，如此重復(fù)，直至選較小者之間再進行兩兩比較，如此重復(fù)，直至選出關(guān)鍵字最小的記錄為止。出關(guān)鍵字最小的記錄為止。 這個過程可用一棵有這個過程可用一棵有n個葉子結(jié)點的個葉子結(jié)點的完全二完全二叉樹叉樹表示例如表示例如P.2791810.4.3 堆排序堆排序 堆的定義堆的定義：n n個元素的序列個元素的序列 kk1 1,k ,k2 2,.,k,.,kn n 當且僅當且僅當滿足下列關(guān)系時，稱為堆。當滿足下列關(guān)系時，稱為堆。 或或 若將此序列對應(yīng)的一維數(shù)組看成是一個若將此序列對

21、應(yīng)的一維數(shù)組看成是一個完全完全二叉樹二叉樹，則堆頂元素必為最大值（或最小值）。，則堆頂元素必為最大值（或最小值）。 iikk212 iikkiikk212 iikk19序列：序列：96,83,27,38,11,20 序列：序列：12,36,24,85,47,30,53,91 對應(yīng)的完全二叉樹對應(yīng)的完全二叉樹 對應(yīng)的完全二叉樹對應(yīng)的完全二叉樹 （大根堆）（大根堆） （小根堆）（小根堆） 在大根堆中，將堆頂和最后一個記錄交換，即得第一趟在大根堆中，將堆頂和最后一個記錄交換，即得第一趟的結(jié)果；再使剩余的結(jié)果；再使剩余n-1個元素的序列重又建成一個堆，則得個元素的序列重又建成一個堆，則得到到n個元素的

22、次大值。如此反復(fù)執(zhí)行，便能得到一個有序序個元素的次大值。如此反復(fù)執(zhí)行，便能得到一個有序序列，這個過程稱為列，這個過程稱為堆排序堆排序。963827832011915330478524361210.4.3 堆排序堆排序20 實現(xiàn)堆排序需要解決兩個問題：實現(xiàn)堆排序需要解決兩個問題： 1）如何由一個無序序列初次建成一個堆？）如何由一個無序序列初次建成一個堆？ 2）如何在一趟排序之后，調(diào)整剩余元素成）如何在一趟排序之后，調(diào)整剩余元素成為為 一個新的堆一個新的堆？10.4.3 堆排序堆排序21 問題問題2解決方法解決方法：輸出堆頂元素之后，用堆中：輸出堆頂元素之后，用堆中最后一個元素替代堆頂，此時根結(jié)點

23、的左右子最后一個元素替代堆頂，此時根結(jié)點的左右子樹均為堆，則需自上而下進行調(diào)整即可。（自樹均為堆，則需自上而下進行調(diào)整即可。（自堆頂至葉子的調(diào)整過程稱為篩選）。堆頂至葉子的調(diào)整過程稱為篩選）。 問題問題1解決方法：解決方法：一個無序序列建堆的過程就一個無序序列建堆的過程就是一個反復(fù)篩選的過程。若將此序列看成是一是一個反復(fù)篩選的過程。若將此序列看成是一個完全二叉樹，則最后一個非終端結(jié)點是第個完全二叉樹，則最后一個非終端結(jié)點是第 n/2 個元素，由此篩選只需從第個元素，由此篩選只需從第 n/2 個元素個元素開始，直到根結(jié)點。開始，直到根結(jié)點。 10.4.3 堆排序堆排序22 typedef SqL

24、ist HeapType; void HeapAdjust(HeapType &H, int s, int m) /由由H.rs.m中記錄的關(guān)鍵字組成的完全二叉樹，根結(jié)點中記錄的關(guān)鍵字組成的完全二叉樹，根結(jié)點 /的左、右子樹均已是堆，現(xiàn)對其進行調(diào)整，使得的左、右子樹均已是堆，現(xiàn)對其進行調(diào)整，使得H.rs.m /成為一個大根堆成為一個大根堆 rc=H.rs; for (j=2*s; j=m; j=j*2) if (j0; -i) HeapAdjust(H,i, H.length); for(i=H.length; i1;-i) H.r1H.ri; HeapAdjust(H,1,i-1);

25、 堆排序最壞情況下，時間復(fù)雜度為堆排序最壞情況下，時間復(fù)雜度為O(nlog2n)10.4.3 堆排序堆排序24 上次課要點：上次課要點：l選擇排序的概念選擇排序的概念l簡單選擇排序的思想和算法簡單選擇排序的思想和算法l堆排序堆排序(重點重點) 1)堆排序的核心算法堆排序的核心算法:篩選篩選 2)堆排序算法堆排序算法 3)堆排序算法時間復(fù)雜度堆排序算法時間復(fù)雜度O(nlog2n)本次課將要講的主要內(nèi)容本次課將要講的主要內(nèi)容:l歸并排序的概念歸并排序的概念l歸并排序的核心操作歸并排序的核心操作:一趟歸并一趟歸并(Merge)l歸并排序的非遞歸實現(xiàn)歸并排序的非遞歸實現(xiàn)l歸并排序的遞歸實現(xiàn)歸并排序的遞

26、歸實現(xiàn)2510.5 歸并排序歸并排序 歸并排序（歸并排序（merge sort）：將兩個或兩：將兩個或兩個以上的個以上的有序表有序表組合成一個新的有序表。組合成一個新的有序表。 假設(shè)初始序列含有假設(shè)初始序列含有n個記錄，則可看成是個記錄，則可看成是n個有序的子序列，每個子序列的長度為個有序的子序列，每個子序列的長度為1，然，然后兩兩歸并，得到后兩兩歸并，得到 n/2 個長度為個長度為2或或1的有序的有序子序列；再兩兩歸并，如此重復(fù)，直到得到一子序列；再兩兩歸并，如此重復(fù)，直到得到一個長度為個長度為n的有序序列為止，該排序方法稱為的有序序列為止，該排序方法稱為2-路歸并排序。路歸并排序。262-

27、路歸并排序示例路歸并排序示例 初始 6 14 12 10 2 18 16 8 第一趟 6 14 10 12 2 18 8 16 第二趟 6 10 12 14 2 8 16 18 第三趟 2 6 8 10 12 14 16 18 27 2路歸并排序中的核心操作路歸并排序中的核心操作是將一維數(shù)組中是將一維數(shù)組中前后相鄰前后相鄰的兩的兩個有序序列個有序序列歸并歸并成一個有序序列。算法如下：成一個有序序列。算法如下： void Merge(Rcdtype SR , Rcdtype &TR ,int i, int m, int n) /將有序的將有序的SRi.m和和SRm+1.n歸并為有序的歸并

28、為有序的TRi.n int j, k; for (j=m+1, k=i; i=m&j=n; k+) if (LQ(SRi.key, SRj.key) TRk=SRi+; else TRk=SRj+; if (i=m) /將剩余的將剩余的SRi.m復(fù)制到復(fù)制到TR TRk.n=SRi.m; if (j=n) /將剩余的將剩余的SRj.n復(fù)制到復(fù)制到TR TRk.n=SRj.n; 10.5 歸并排序歸并排序-核心操作核心操作2810.5 歸并排序歸并排序-非遞歸實現(xiàn)非遞歸實現(xiàn) 歸并排序歸并排序算法思想算法思想： 1）開始時先將）開始時先將n個記錄看成個記錄看成n個長度為個長度為1的已排好的

29、已排好 序的表；序的表； 2）將相鄰的表兩兩合并，得到長度為）將相鄰的表兩兩合并，得到長度為2的（的（n/2） 個有序表；個有序表； 3）進一步再將相鄰表兩兩合并，得到長度為）進一步再將相鄰表兩兩合并，得到長度為4的的 （n/4）個有序表；）個有序表； 如此重復(fù)下去，直至所有記錄均合并到一個如此重復(fù)下去，直至所有記錄均合并到一個 長度為長度為n的有序表為止，就完成了排序。的有序表為止，就完成了排序。2910.5 歸并排序歸并排序-非遞歸實現(xiàn)非遞歸實現(xiàn)mergepass(Rcdtype R ,Rcdtype &R1 , int length) /對對R做一趟歸并做一趟歸并,結(jié)果放在結(jié)果放

30、在R1中中,子文件長度為子文件長度為length int i=0, j; / i 指向第一對子文件的起點指向第一對子文件的起點 while (i+2*length-1n) /歸并長度為歸并長度為length的兩個相鄰子文件的兩個相鄰子文件 merge(R, R1, i, i+length-1, i+2*length-1); i=i+2*length; /指向下一對子文件起始點指向下一對子文件起始點 if (i+length-1n-1) /剩下最后兩個子文件剩下最后兩個子文件,其中一個長度小于其中一個長度小于length merge(R, R1, i, i+length-1, n-1); els

31、e for (j=i; jn; j+) R1j=Rj; /最后一個文件復(fù)制到最后一個文件復(fù)制到R1中中 3010.5 歸并排序歸并排序-非遞歸實現(xiàn)非遞歸實現(xiàn)Void Mergesort(rcdtype R ) /對對R進行二路歸并排序進行二路歸并排序,結(jié)果仍在結(jié)果仍在R中中 int length=1; while (length=n) mergepass(R,R1,length); /一趟歸并，結(jié)果在一趟歸并，結(jié)果在R1中中 length=2*length; mergepass(R1,R,length); /再次歸并再次歸并,結(jié)果在結(jié)果在R中中 length=2*length; 3110.5

32、歸并排序歸并排序-遞歸實現(xiàn)遞歸實現(xiàn)請同學們思考：請同學們思考： 1、遞歸求解的三個條件？、遞歸求解的三個條件？ 2、歸并排序中如何體現(xiàn)這三個條件？、歸并排序中如何體現(xiàn)這三個條件？3210.5 歸并排序歸并排序-遞歸實現(xiàn)遞歸實現(xiàn)void Msort(Rcdtype SR ,Rcdtype &TR1 , int s, int t) /將將SRs.t歸并排序為歸并排序為TR1s.t if (s= =t) TR1s=SRs; /遞歸出口遞歸出口 else m=(s+t)/2; /將將SRs.t平分為平分為SRs.m和和SRm+1.t Msort(SR, TR2,s,m); Msort(SR,T

33、R2,m+1,t); Merge(TR2,TR1,s,m,t); /將將TR2s.m和和TR2m+1.t /歸并到歸并到TR1s.t void MergeSort(SqList &L) /對表對表L作歸并排序作歸并排序 Msort(L.r, L.r, 1, L.length); 3310.5 歸并排序歸并排序-算法分析算法分析l 時間復(fù)雜度：時間復(fù)雜度：第第 i 趟歸并后，有序子文件長度為趟歸并后，有序子文件長度為2i，因，因此此,對有對有n個記錄的文件排序，必須做個記錄的文件排序，必須做 趟歸并，趟歸并，每趟歸并所花的時間是每趟歸并所花的時間是O(n);因此二路歸并排序的時間復(fù)因此二

34、路歸并排序的時間復(fù)雜性為雜性為O(nlog2n )。l 空間復(fù)雜度：空間復(fù)雜度：歸并排序需要和待排記錄數(shù)量的歸并排序需要和待排記錄數(shù)量的輔輔 助空間，即空間復(fù)雜度為助空間，即空間復(fù)雜度為O(n)l 穩(wěn)定性問題：穩(wěn)定性問題：歸并排序是歸并排序是穩(wěn)定的穩(wěn)定的。 思考：用遞歸實現(xiàn)的算法如何改進？思考：用遞歸實現(xiàn)的算法如何改進？nlog23410.6 基數(shù)排序基數(shù)排序本小節(jié)主要內(nèi)容本小節(jié)主要內(nèi)容:l基數(shù)排序與其他排序的不同之處基數(shù)排序與其他排序的不同之處l多關(guān)鍵字排序的兩種方法多關(guān)鍵字排序的兩種方法l鏈式基數(shù)排序的兩種主要操作鏈式基數(shù)排序的兩種主要操作:分配和收集分配和收集l鏈式基數(shù)排序的算法鏈式基數(shù)

35、排序的算法3510.6 基數(shù)排序基數(shù)排序 基數(shù)排序與其他排序的不同之處基數(shù)排序與其他排序的不同之處: 前面講到的四大類排序（插入、交換、選擇、前面講到的四大類排序（插入、交換、選擇、歸并）主要通過關(guān)鍵字間的歸并）主要通過關(guān)鍵字間的比較和移動比較和移動這兩種操這兩種操作，而基數(shù)排序不需要進行關(guān)鍵字間的比較。作，而基數(shù)排序不需要進行關(guān)鍵字間的比較?；鶖?shù)排序數(shù)排序(Radix Sorting) 是借助多關(guān)鍵字排序的思是借助多關(guān)鍵字排序的思想對單關(guān)鍵字進行的排序方法。想對單關(guān)鍵字進行的排序方法。3610.6 基數(shù)排序基數(shù)排序-概念概念l多關(guān)鍵字排序方法有兩種：多關(guān)鍵字排序方法有兩種： (1)最高位優(yōu)

36、先最高位優(yōu)先(Most Significant Digit first )MSD (2)最低位優(yōu)先最低位優(yōu)先(Least Significant Digit first )LSDl 最低位優(yōu)先最低位優(yōu)先(Least Significant Digit first )LSD 設(shè)：每個記錄中含有設(shè)：每個記錄中含有d個關(guān)鍵字個關(guān)鍵字(K0,K1,K2,Kd-1) K0 稱為最主位關(guān)鍵字，稱為最主位關(guān)鍵字， Kd-1 稱為最次位關(guān)鍵字。稱為最次位關(guān)鍵字。 最低位優(yōu)先最低位優(yōu)先LSD是從最次位關(guān)鍵字是從最次位關(guān)鍵字Kd-1起進行排序起進行排序,然后再對高一位的關(guān)鍵字然后再對高一位的關(guān)鍵字Kd-2進行排序

37、進行排序,依次重復(fù)依次重復(fù),直到對直到對K0位進行排序后便成為一個有序序列。位進行排序后便成為一個有序序列。3710.6 基數(shù)排序基數(shù)排序-鏈式基數(shù)排序鏈式基數(shù)排序鏈式基數(shù)排序：鏈式基數(shù)排序：用鏈表作存儲結(jié)構(gòu)，并借助用鏈表作存儲結(jié)構(gòu)，并借助分配和收集分配和收集兩種兩種操作對單關(guān)鍵字進行排序的一種方法。操作對單關(guān)鍵字進行排序的一種方法。具體方法：具體方法：1. 用靜態(tài)鏈表用靜態(tài)鏈表存儲存儲n個待排記錄個待排記錄,并令表頭指針指向第一個記錄；并令表頭指針指向第一個記錄；2. 第一趟分配第一趟分配對最低數(shù)位（個位）進行，改變記錄的指針將鏈對最低數(shù)位（個位）進行，改變記錄的指針將鏈 表中的記錄分配到表

38、中的記錄分配到10個鏈表中個鏈表中,每個隊列中所有記錄的關(guān)鍵字每個隊列中所有記錄的關(guān)鍵字 個位數(shù)相等，個位數(shù)相等，fi和和ei分別為第分別為第i個隊列的頭指針和尾指針；個隊列的頭指針和尾指針； 第一趟收集第一趟收集是改變所有非空隊列的隊尾記錄的指針域，令其是改變所有非空隊列的隊尾記錄的指針域，令其 指向下一個非空隊列的隊頭記錄，重新將指向下一個非空隊列的隊頭記錄，重新將10個隊列中的記錄個隊列中的記錄 鏈接成一個鏈表；鏈接成一個鏈表；3.第二趟分配，第二趟收集第二趟分配，第二趟收集及第三趟分配和第三趟收集分別對及第三趟分配和第三趟收集分別對 十位數(shù)和百位數(shù)進行，過程相同。十位數(shù)和百位數(shù)進行，過

39、程相同。3810.6 基數(shù)排序基數(shù)排序-數(shù)據(jù)結(jié)構(gòu)定義數(shù)據(jù)結(jié)構(gòu)定義#define MAX_NUM_OF_KEY 8 /關(guān)鍵字項數(shù)的最大值關(guān)鍵字項數(shù)的最大值#define RADIX 10 /關(guān)鍵字基數(shù)關(guān)鍵字基數(shù)#define MAX_SPACE 10000 typedef struct KeysType keysMAX_NUM_OF_KEY; /關(guān)鍵字關(guān)鍵字 InfoType otheritems; int next; SLCell; /靜態(tài)鏈表的靜態(tài)鏈表的結(jié)點類型結(jié)點類型 typedef struct SLCell rMAX_SPACE; /靜態(tài)鏈表的可利用空間，靜態(tài)鏈表的可利用空間，r0為頭

40、結(jié)點為頭結(jié)點 int keynum; /記錄的當前關(guān)鍵字個數(shù)記錄的當前關(guān)鍵字個數(shù) int recnum; /靜態(tài)鏈表的當前長度靜態(tài)鏈表的當前長度 SLList; /靜態(tài)靜態(tài)鏈表類型鏈表類型 typedef int ArrTypeRADIX;39 Void Distribute(SLCell &r, int i, ArrType &f, ArrType &e) /靜態(tài)鏈表靜態(tài)鏈表L的的r域中記錄已按域中記錄已按(keys0,keysi-1)有序有序 /本算法按第本算法按第i個關(guān)鍵字個關(guān)鍵字keyi建立建立RADIX個子表，使同一子表個子表，使同一子表 /中記錄中記錄keyi的相同；的相同；f0.RADIX-1和和e0.RADIX-1分別指分別指 /向各子表中第一個和最后一個記錄向各子表中第一個和最后一個記錄 int j, p; for (j=0;jRadix; +j) fj=0; /各子表初始化為空表各子表初始化為空表 for (p=r0.next; p; p=rp.next) j=ord(rp.keyi); /將第將第i個關(guān)鍵字映射到個關(guān)鍵字映射到0.RADIX-1 if