第十章排序PPT课件

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