1、普通高等教育普通高等教育“十一五十一五”國家級規劃教材國家級規劃教材第十章第十章 排序排序 10.1 基本概念基本概念 10.2 內部排序內部排序 10.3 內部排序方法比較內部排序方法比較 10.4 外部排序簡介外部排序簡介普通高等教育普通高等教育“十一五十一五”國家級規劃教材國家級規劃教材10.1 基本概念基本概念 關鍵字關鍵字(key)： 記錄的某一個可以用來標識一個數據記錄的某一個可以用來標識一個數據元素的數據項元素的數據項 排序（排序（Sorting）：）：把一組記錄，按照記錄中某個關把一組記錄，按照記錄中某個關鍵字進行有序（遞增或遞減）排列的過程鍵字進行有序（遞增或遞減）排列的過程

2、 內部排序內部排序 ：文件較小時，排序在內存中完成，不涉及文件較小時，排序在內存中完成，不涉及外存的排序方法稱為內部排序外存的排序方法稱為內部排序 外部排序外部排序 ：文件比較大，排序需要內存和外存，稱這文件比較大，排序需要內存和外存，稱這種排序為外部排序種排序為外部排序 普通高等教育普通高等教育“十一五十一五”國家級規劃教材國家級規劃教材排序方法的分類：排序方法的分類：按是否涉及數據的內、外存交換按是否涉及數據的內、外存交換策略劃分內部排序方法策略劃分內部排序方法 內部排序 外部排序 插入排序選擇排序交換排序歸并排序分配排序 普通高等教育普通高等教育“十一五十一五”國家級規劃教材國家級規劃教

3、材 排序算法的基本操作排序算法的基本操作(1) 比較兩個關鍵字的大小比較兩個關鍵字的大小 (2) 改變指向記錄的指針或移動記錄本身改變指向記錄的指針或移動記錄本身 待排文件的常用存儲方式待排文件的常用存儲方式（1）以順序表作為存儲結構）以順序表作為存儲結構（2）以鏈表作為存儲結構）以鏈表作為存儲結構（3）用順序的方式存儲待排序的記錄，并建立輔助表）用順序的方式存儲待排序的記錄，并建立輔助表 排序算法性能評價排序算法性能評價 執行時間和所需的輔助空間執行時間和所需的輔助空間 算法本身的復雜程度算法本身的復雜程度普通高等教育普通高等教育“十一五十一五”國家級規劃教材國家級規劃教材10.2 內部排序

4、內部排序10.2.1 插入排序插入排序 概念：概念：按關鍵字大小將一個記錄插入到一個有序的文按關鍵字大小將一個記錄插入到一個有序的文件中的適當位置，并且插入后使文件仍然是有序的件中的適當位置，并且插入后使文件仍然是有序的 分類：分類：直接插入排序直接插入排序 折半插入排序折半插入排序 希爾排序希爾排序 普通高等教育普通高等教育“十一五十一五”國家級規劃教材國家級規劃教材直接插入排序直接插入排序概念：概念：每一次將一個待排序的記錄，按其關鍵字值的每一次將一個待排序的記錄，按其關鍵字值的大小插入到已經排序的部分文件中適當的位置上，直大小插入到已經排序的部分文件中適當的位置上，直到全部插入完成到全部

5、插入完成 算法：算法：1.InsertSort(Recordnode r,int n)2. for(i=2;i=n;+i)3. if(riri-1) 4. r0=ri;5. for(j=i-1;r0rj;-j)6. rj+1=rj; /*記錄后移*/7. rj+1=r0; /*插入到正確位置*/8. 9.普通高等教育普通高等教育“十一五十一五”國家級規劃教材國家級規劃教材 事例：事例：普通高等教育普通高等教育“十一五十一五”國家級規劃教材國家級規劃教材折半插入排序折半插入排序 概念：概念：插入的記錄的關鍵字和有序區間的中點處記錄插入的記錄的關鍵字和有序區間的中點處記錄的關鍵字作比較，若二者相等

6、則查找成功，否則可以根的關鍵字作比較，若二者相等則查找成功，否則可以根據比較的結果來確定下次的查找區間，若插入的記錄關據比較的結果來確定下次的查找區間，若插入的記錄關鍵字小于有序序列中點的記錄關鍵字，那么下次查找的鍵字小于有序序列中點的記錄關鍵字，那么下次查找的區間在中點記錄前半部分，否則在中點記錄的后半部分；區間在中點記錄前半部分，否則在中點記錄的后半部分；然后在新的查找區間進行同樣的查找，經過多次折半查然后在新的查找區間進行同樣的查找，經過多次折半查找，直到找到插入位置為止；找，直到找到插入位置為止；普通高等教育普通高等教育“十一五十一五”國家級規劃教材國家級規劃教材 算法：算法：1. B

7、insertSort(Recordnode r,int n)2. 3. for(i=2;i=n;+i)4. 5. r0=ri;6. low=1;high=i-1;7. while(low=high)8. 9. m=( low + high )/2;10. if (r0=high+1;-j)14. rj+1=rj; /*記錄后移*/15. rhigh+1=r0; /*插入*/16. 17. 普通高等教育普通高等教育“十一五十一五”國家級規劃教材國家級規劃教材 事例：事例：在序列在序列01 14 19 23 55 84 92已排好序的基礎已排好序的基礎上，將元素上，將元素15插入到序列中插入到序列

8、中 普通高等教育普通高等教育“十一五十一五”國家級規劃教材國家級規劃教材希爾排序希爾排序 概念：概念：不斷的把待排序的一組記錄按間隔值分成若干不斷的把待排序的一組記錄按間隔值分成若干小組，然后對同一組的記錄進行排序；即首先設置一個小組，然后對同一組的記錄進行排序；即首先設置一個記錄的間隔值記錄的間隔值d1，把全部記錄按此間隔值從第一個記錄，把全部記錄按此間隔值從第一個記錄起進行分組，所有相隔為起進行分組，所有相隔為d的元素在同一小組中，再進的元素在同一小組中，再進行組內排序；然后再設置另一個間隔值行組內排序；然后再設置另一個間隔值d2（d1d2），），重新將整個組分成若干個組，再對各組進行組內

9、排序，重新將整個組分成若干個組，再對各組進行組內排序，多次重復以后，直到間隔值多次重復以后，直到間隔值d1為止為止 普通高等教育普通高等教育“十一五十一五”國家級規劃教材國家級規劃教材 算法：算法：1. ShellSort(Recordnode r,int n)2. 3. int i,j,d; int bool; int x; 4. d=n;5. do6. d=d/2;7. do8. bool=1;9. for(i=1;irj)12. x=ri;13. ri=rj; rj=x;14. bool=0;15. 16. wlile(!bool)17. while(d1)18. 普通高等教育普通高等教

10、育“十一五十一五”國家級規劃教材國家級規劃教材 事例：事例：普通高等教育普通高等教育“十一五十一五”國家級規劃教材國家級規劃教材10.2.2 冒泡排序冒泡排序 概念：概念：將待排序的序列中第一個記錄的關鍵字將待排序的序列中第一個記錄的關鍵字r1.key與第二個關鍵字與第二個關鍵字r2.key進行比較進行比較(從小到大從小到大)，如果，如果r1.keyr2.key，則交換，則交換r1和和r2記錄序列中的位置，記錄序列中的位置，否則不交換；然后再接著對當前序列中的第二個記錄和否則不交換；然后再接著對當前序列中的第二個記錄和第三個記錄作同樣的比較，依此類推，直到序列中最后第三個記錄作同樣的比較，依此

11、類推，直到序列中最后兩個記錄處理完為止兩個記錄處理完為止 普通高等教育普通高等教育“十一五十一五”國家級規劃教材國家級規劃教材 算法：算法：1. Bubblesort(Recordnode r,int n)2. 3. int i,j,flag; int temp;4. flag=1;5. for (i=1;in & flag= =1;i+)6. 7. falg=0;8. for(j=0;jrj+1.key)11. 12. flag=1; temp=rj; rj=rj+1; rj+1=temp;13. 14.15. 16. 普通高等教育普通高等教育“十一五十一五”國家級規劃教材國家級規劃

12、教材 事例：事例：有八個記錄，初始關鍵字序列為有八個記錄，初始關鍵字序列為5，7，3，8，2，9，1，4，用冒泡排序對它進行排序，用冒泡排序對它進行排序 普通高等教育普通高等教育“十一五十一五”國家級規劃教材國家級規劃教材10.2.3 快速排序快速排序 概念：概念：從兩頭向中間掃描，同時交換與基準記錄逆序從兩頭向中間掃描，同時交換與基準記錄逆序的記錄；在待排序的的記錄；在待排序的n個記錄中任取一個記錄（通常取個記錄中任取一個記錄（通常取第一個記錄），把該記錄放入最終位置后，序列被這個第一個記錄），把該記錄放入最終位置后，序列被這個記錄分割成兩部分，所有關鍵字比該記錄關鍵字小的放記錄分割成兩部分

13、，所有關鍵字比該記錄關鍵字小的放置在前一部分，所有比它大的放置在后一部分，并把該置在前一部分，所有比它大的放置在后一部分，并把該記錄排在這兩部分的中間，這個過程稱為一次快速排序；記錄排在這兩部分的中間，這個過程稱為一次快速排序；對所分的兩部分分別重復上述過程，直至每部分內只有對所分的兩部分分別重復上述過程，直至每部分內只有一個記錄為止一個記錄為止 普通高等教育普通高等教育“十一五十一五”國家級規劃教材國家級規劃教材 算法：算法：1. void quicksort（Recordlist &L,int low,int high）2. if (lowhigh)3. 4. Partition(

14、L,low,high);5. If (le_lowle_high) quicksort(L, low, le_high);6. If (Ri_lowRi_high) quicksort(L, Ri_low, high);7. 8. 1. int Partition(Recordnode r,int low,int high)2. /*進行一次快速排序，使一個記錄到位*/ 3. int Le_low，Le_high，Ri_low，Ri_high4. int x，i，j；/*定義一個臨時變量*/5. i=low;6. j=high; /*用r0.m.length-1存放關鍵字*/7. x=ri;普

15、通高等教育普通高等教育“十一五十一五”國家級規劃教材國家級規劃教材8.while(ij)9.10. while(i=r0)11. -j;12. ri=rj; /*將關鍵字比x小的記錄移到前面*/13. while(ij & rj.key=r0)14. +i;15. rj=ri; /將關鍵字比x大的記錄移到后面*/16. 17.Lri=x;18.Le_low=low;19.Le_high=i-1;20.Ri_low=j+1;21.Ri_high=high;22.Return(Le_low, Le_high，Ri_low，Ri_high)；23.普通高等教育普通高等教育“十一五十一五”國家

16、級規劃教材國家級規劃教材 事例：事例：28，19，27，48，56，12，10，25，20，50，對其進行快速排序對其進行快速排序普通高等教育普通高等教育“十一五十一五”國家級規劃教材國家級規劃教材普通高等教育普通高等教育“十一五十一五”國家級規劃教材國家級規劃教材10.2.4 選擇排序選擇排序直接選擇排序：直接選擇排序：算法思想：算法思想：待排序的所有記錄中，選取關鍵字最小的記錄并待排序的所有記錄中，選取關鍵字最小的記錄并將它與原始序列的第一個記錄交換位置，然后從去掉了關鍵字最將它與原始序列的第一個記錄交換位置，然后從去掉了關鍵字最小的記錄的剩余記錄中選擇關鍵字最小的記錄與原始記錄的第二小的

17、記錄的剩余記錄中選擇關鍵字最小的記錄與原始記錄的第二個記錄交換位置個記錄交換位置 算法：算法：1.void SelectSort(Recordnode r,int n)2. int i,j,k; int w;3. for(i=1;i=n-1;i+)4. k=i;5. for(j=i+1;j=n;j+)6. 7. if(rj=1;l- -)6. sift(r,l,n);7. for(l=n;l=2;l- -)8. w=rl;9. rl=r1;10. r1=w;11. sift(r,1,l-1);12. 13. 普通高等教育普通高等教育“十一五十一五”國家級規劃教材國家級規劃教材/*篩選算法篩選算

18、法*/1. void sift(Recordnode r,int l,int m) 2. 3. int i,j,x;4. i=l; j=2*i; x=ri;5. while(j=m)6. 7. if(jm & rjrj+1) j+;8. if(xrj)9. 10. ri=rj;11. i=j;12. j=2*i;13. 14. else j=m+1;15. 16. ri=x;17. 普通高等教育普通高等教育“十一五十一五”國家級規劃教材國家級規劃教材 事例：事例：假設一數組的原始數據為：假設一數組的原始數據為： 用完全二叉樹表示用完全二叉樹表示 普通高等教育普通高等教育“十一五十一五”

19、國家級規劃教材國家級規劃教材 排序過程：排序過程：7814 7144 8758933681264537897889 7144 8756833141468537298978 7144 8756833144168537293378 7144 875681491685372普通高等教育普通高等教育“十一五十一五”國家級規劃教材國家級規劃教材7875 7144 8336814156893721475 7144 8336825689377568 7144 8331458629374468 71 83314786293普通高等教育普通高等教育“十一五十一五”國家級規劃教材國家級規劃教材716844 833

20、1468729386844331438729683344 8148972383344143972普通高等教育普通高等教育“十一五十一五”國家級規劃教材國家級規劃教材4433814793214338293331489238143214823普通高等教育普通高等教育“十一五十一五”國家級規劃教材國家級規劃教材10.2.5 歸并排序歸并排序 歸并：歸并：兩個或兩個以上的已排序文件合并成一個有序兩個或兩個以上的已排序文件合并成一個有序文件的過程文件的過程 算法思想：算法思想：合并時依次比較合并時依次比較ri和和rj的關鍵字，取關的關鍵字，取關鍵字較小的記錄復制到鍵字較小的記錄復制到s中，將指向被復制記

21、錄的指針中，將指向被復制記錄的指針加加1并將指向復制位置的指針加并將指向復制位置的指針加1，重復這一過程；直至，重復這一過程；直至全部記錄被復制到全部記錄被復制到slowhigh中為止中為止 普通高等教育普通高等教育“十一五十一五”國家級規劃教材國家級規劃教材 算法：算法：1. void Merge(Recordnode r，int l，int m，int h，Recordnode s)2. int k,i,j;3. k=l; i=l; j=m+1;4. while(i=m&j=high)5. 6. if(rim)普通高等教育普通高等教育“十一五十一五”國家級規劃教材國家級規劃教材17

22、. while(j=h ）18. 19. sk=rj;20. j+; k+;21. 22. else23. while(i=m)/*第一個子文件還有剩余記錄未復制*/24. 25. sk=ri;26. i+; k+;27. 28. 普通高等教育普通高等教育“十一五十一五”國家級規劃教材國家級規劃教材一次歸并排序算法一次歸并排序算法1.Void passmerge (recordnode x ，recordnode s ，int n，int L)2.3.int i=1，j；4.while（i+2*L-1=n）5./*依次對相鄰有序子表進行歸并*/6.merge(x，s，i，i+L-1，I+2*L

23、-1)；7.i=i+2*L；8.9.if（i+L-1=n）10. Merge(x，s，I，i+L-1，n)；/*長度不足L的子表*/11. else12. for（j=i；j=n；j+）sj=xj；13. 普通高等教育普通高等教育“十一五十一五”國家級規劃教材國家級規劃教材二路歸并算法二路歸并算法1.void Mergesort（recordnode x ，recordnode s ，int n）2.3. int i，len；4. len=1；5. while（lenn）6. 7. passmerge（r，s，n，len）；）；8. for（i=1，i=n；i+）9. ri=si；10. le

24、n=len*2；11. 12. 普通高等教育普通高等教育“十一五十一五”國家級規劃教材國家級規劃教材 事例：事例：有包含有包含10個記錄的待排序列，其關鍵字值為：個記錄的待排序列，其關鍵字值為：26 5 77 1 61 11 59 15 48 19，采用歸并算法對其排，采用歸并算法對其排序序 普通高等教育普通高等教育“十一五十一五”國家級規劃教材國家級規劃教材10.2.6 基數排序基數排序 引例：引例：設一組原始數據如下所示：設一組原始數據如下所示： (1)依照十位數的大小排序依照十位數的大小排序 普通高等教育普通高等教育“十一五十一五”國家級規劃教材國家級規劃教材 (2)個位數的大小排序個位

25、數的大小排序 最后結果：最后結果：普通高等教育普通高等教育“十一五十一五”國家級規劃教材國家級規劃教材 算法思想：算法思想：設記錄設記錄ri的關鍵字的關鍵字ki時，一個時，一個ki是由是由d位位數字組成，即數字組成，即ki =Ki1Ki2Kid，每一個子關鍵字表示關，每一個子關鍵字表示關鍵字的一位，其中鍵字的一位，其中Ki1為最高位，為最高位，Kid為最低位，每一位為最低位，每一位的值都在的值都在OKijr-1（1jd）范圍內，則就稱）范圍內，則就稱r為基數為基數 ；若關鍵字若關鍵字Ki中的中的0 Kij r-1，則根據選擇的基數，設定，則根據選擇的基數，設定r個隊列；然后按個隊列；然后按LS

26、D法，先把每個記錄的最低位關鍵字法，先把每個記錄的最低位關鍵字分別分配到相應的隊列中去，再把分別分配到相應的隊列中去，再把r個隊列從小到大首個隊列從小到大首尾相接收集起來；這樣就記錄按最低位尾相接收集起來；這樣就記錄按最低位Kid的值排好序，的值排好序，稱為第一次分配收集稱為第一次分配收集 ；在此基礎上，再按次低位進行排；在此基礎上，再按次低位進行排序；依次類推，由低位向高位，每次都是根據關鍵字的序；依次類推，由低位向高位，每次都是根據關鍵字的一位并在前一次的基礎上對文件中所有的記錄進行排序；一位并在前一次的基礎上對文件中所有的記錄進行排序；直到最高位，這樣就完成了基數排序的全過程直到最高位，

27、這樣就完成了基數排序的全過程 普通高等教育普通高等教育“十一五十一五”國家級規劃教材國家級規劃教材 算法：算法：#define d 8 /*d為關鍵字的個數*/#define Radix 10#define Max_Space 1000 typedef struct int keysd;/*關鍵字數組*/ int next; Recordnode; /*結點類型*/Recordnode fRadix,rRadix; typedef struct Recordnode QMax_Space; /* 待排序序列*/ int key_num;/*記錄的當前關鍵字個數*/ int rec_Length

28、;/*靜態鏈表的當前長度*/ SLList;普通高等教育普通高等教育“十一五十一五”國家級規劃教材國家級規劃教材1.void Distribute(Recordnode Q, int i, Recordnode f, Recordnode r)2.3. Recordnode *p4. for(j=0; jRadix; +j)5. 6. fj=0;7. rj=0；8. /*初始化*/9. for( p=Q0.next; p; p=Qp.next)10. 11. j=ord(Qp.keysi); if(fj= = Null) fj=p;12. else Qrj.next=p;13. rj =p;14. 15. 普通高等教育普通高等教育“十一五十一五”國家級規劃教材國家級規劃教材1. void Collect( Recordnode Q, int i, Recordnode f, Recordnode r)2. 3. for(j=0;!fj;j=succ(j); /*找到第一個非空子表，用succ()求后繼*/4. Q0.next=fj;5. t=rj;6. while(jRadix)7. 8. j=succ(j);9. while（fj