数据结构第10章排序

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,127,DATA STRUCTURE,2024/11/27,1,第,10,章 排序,2024/11/27,2,本章目录,10.1,概述,10.2,插入排序,10.2.1,直接插入排序,10.2.2,折半插入排序,*,10.2.3,二路插入排序 *,10.2.4,表插入排序,10.2.5,希尔排序,10.3,交换排序,10.3.1,起泡排序,10.3.2,快速排序,10.4,选择排序,10.4.1,直接选择排序,10.4.2,树形选择排序,10.4.3,堆排序,10.5,归并排序,10.6,分配排序,10.7,内部排序方法的比较,10.8,外部排序,10.8.1,文件管理,10.8.2,外部排序,10.8.3,多路归并排序,10.8.4,置换选择排序,*,10.8.5,最佳归并树,*,10.8.6,磁带排序,2024/11/27,3,主要内容,知识点,1,、,排序的定义，排序可以看作是线性表的一种操作,2,、排序的分类，稳定排序与不稳定排序的定义。,3,、插入排序（直接插入、,对分插入,、二路插入、表插入、希尔插入排序）。,4,、交换排序（冒泡排序、,快速排序,）。,5,、选择排序（简单选择排序、树形选择排序、,堆排序,）。,6,、归并排序、基数排序。,7,、外部排序,重点难点,1,、各种排序所基于的基本思想。,2,、排序性能的分析，是否是稳定排序。,3,、,折半插入、希尔排序,。,4,、,快速排序,。,5,、,堆排序,。,6,、败者树、置换选择排序、,最佳归并树,。,7,、对每种排序方法的学习，能举一反三。,2024/11/27,4,基本概念,排序：,假设含,n,个记录的序列为,R,1, R,2,R,n,，,其相应的关键字序列为, K,1, K,2,K,n,，,这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系,Ks,1,Ks,2,Ks,n,，按此固有关系将,n,个记录的序列重新排列为, Rs,1, Rs,2,Rs,n,的操作称作,排序,。,2024/11/27,5,基本概念,稳定排序,：,若,K,i,为关键字，,K,i,=K,j,（,i,j,），且在排序前的序列中,R,i,领先于,R,j,。经过排序后，,R,i,与,R,j,的相对次序保持不变（即,R,i,仍领先于,R,j,），则称这种排序方法是,稳定的,，否则称之为,不稳定的。,内部排序,：若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序,外部排序,：若参加排序的记录数量很大，整个序列的排序过程不可能一次在内存中完成，则称此类排序问题为外部排序,2024/11/27,6,排序的类型定义,#define n,待排序记录的个数,typedef struct,int key,;,AnyType other; ,记录其它数据域, RecType;,RecType Rn+1;,2024/11/27,7,基本思想,：,假定第一个记录有序,，,从第,2,个记录开始，将待排序的记录插入到有序序列中，使有序序列逐渐扩大，直至所有记录都进入有序序列中。,插入排序,插入排序种类,：,直接插入排序,折半插入排序,二路插入排序,表插入排序,希尔排序,2024/11/27,8,直接插入排序,基本思想,：将记录,Ri(2=i=n),插入到有序子序列,R1.i-1,中，使记录的有序序列从,R1.i-1,变为,R1.i,2024/11/27,9,示例,初始关键字序列：,51, 33 62 96 87 17 28 51,i=2(33) ,33,51 62 96 87 17 28 51,i=3(62) 33 51,62, 96 87 17 28 51,i=4(96) 33 51 62,96, 87 17 28 51,i=5(87) 33 51 62,87,96 17 28 51,i=6(17) ,17,33 51 62 87 96 28 51,i=7(28) 17,28,33 51 62 87 96 51,i=8(51,) 17 28 33 51,51,62 87 96,2024/11/27,10,一趟,直接插入排序算法,void StrOnePass(RecType R,，,int i),已知,R1.i-1,中的记录按关键字非递减有序排列，本算法,插入,Ri,使,R1.i,中的记录按关键字非递减有序排列,R0=Ri; j=i-1; ,将待排序记录放进监视哨,x=R0.key;,从后向前查找插入位置，将大于待排序记录向后移动,while (x Rj.key), Rj+1=Rj; j-; ,记录后移,R,j+1,=R0; ,将待排序记录放到合适位置,StrOnePass,2024/11/27,11,直接插入排序算法,void StrInsSort1(RecType R,，,int n),本算法对,R1.n,进行直接插入排序,for(i=2;i=n;i+) ,假定第一个记录有序,StrOnePass(R,，,i),；,2024/11/27,12,直接插入排序性能分析,最坏情况,比较次数为,=(n+2)(n-1)/2,移动,次数为,=(n+4)(n-1)/2,最好情况,比较次数为,n-1,次,移动,次数为,2,（,n,-,1,）次,2024/11/27,13,直接插入排序的优缺点,直接插入排序,算法简单,，当待排序记录数量,n,很小时，局部有序时，较为适用。,当,n,很大时，其效率不高,。,若对直接插入排序算法进行改进，可从减少“比较”和“移动”次数这两方面着手,。,折半存入排序,、,二路插入排序,、,表插入排序,、,希尔排序,都是对直接插入排序的改进,。,2024/11/27,14,折半插入排序,void BinsSort(RecType R,，,int n),对,R1.n,进行折半插入排序, for(i=2;i=n;i+) ,假定第一个记录有序, R0=Ri; ,将待排记录,Ri,暂存到,R0,low=1; high=i-1; ,设置折半查找的范围,Rlow.high,while (low=high),m=(low+high)/2; ,折半,if(R0.keyhigh; j-) Rj+1 = Rj; ,记录后移,Rhigh+1 = R0; ,插入,for,BinsSort,2024/11/27,15,折半插入排序性能分析,减少了比较次数，移动次数不变。,时间复杂度仍为,O,（,n,2,）。,2024/11/27,16,在对一组记录,（,54,，,38,，,96,，,23,，,15,，,72,，,60,，,45,，,83,）,进行直接排序时，当把第,7,个记录,60,插入到有序表时，为寻找插入位置需比较多少次,自测题,1,2024/11/27,17,二路插入排序,对折半插入排序改进，减少了移动记录的次数，但它要借助,n,个记录的辅助空间，即其空间复杂度为,O,（,n,）。,基本思想：另设一数组,d,，将,R1,赋值给,d1,，并将,d1,看作排好序的中间记录，从第二个记录起依次将关键字小于,d1,的记录插入,d1,之前的有序序列，将关键字大于,d1,的记录插入,d1,之后的有序序列。,借助两个变量,first,和,final,来指示排序过程中有序序列第一个记录和最后一个记录在,d,中的位置。,2024/11/27,18,初始关键字序列：,51 33 62 96 87 17 28,51,i=1 51,firstfinal,i=2 51 ,33,final first,i=3 51,62, 33,final first,i=4 51 62,96, 33,final first,i=5 51 62,87,96 33,final first,i=6 51 62 87 96 ,17,33,final first,i=7 51 62 87 96 17,28,33,final first,i=8 51,51,62 87 96 17 28 33,final first,2024/11/27,19,二路插入排序算法,void BiInsertSort(RecType R,，,int n),二路插入排序的算法,int dn+1; ,辅助存储,d1= R1;first=1;final=1;,for(i=2;i=d1.key) ,插入后部,low=1;high=final;,while (low=high) ,折半查找插入位置, m=(low+high)/2;,if(Ri.key=high+1;j-) dj+1 = dj; ,移动元素,dhigh+1=Ri; final+; ,插入有序位置,2024/11/27,20,else if(first=1) ,插入前部, first=n; dn=Ri; ,else low=first;high=n;,while (low=high), m=(low+high)/2;,if(Ri.key dm.key) high=m-1;,else low=m+1;,while,for (j=first;j=high;j+) dj-1 = dj;,移动元素,dhigh=Ri; first-;,if, if, /for,2024/11/27,21,表插入排序,静态链表,#define n,待排序记录的个数,typedef struct, int key;,AnyType other; ,记录其他数据域,int next;, STListType;,STListType SLn+1;,2024/11/27,22,表插入排序算法,void ListInsSort(STListType SL,int n),对记录序列,SL1.n,作表插入排序。,SL0.key=MAXINT ;,SL0.next=1; SL1.next=0;,for(i=2; i=n; i+ ) ,查找插入位置,j=0;,for(k=SL0.next; SLk.key=SLi.key; ),j=k, k=SLk.next; ,SLj.next=i; SLi.next=k;,结点,i,插入在结点,j,和结点,k,之间,for,ListInsSort,2024/11/27,23,表物理排序,void Arrange(STListType SL,，,int n),调整静态链表,SL,中各结点的指针值，使记录按关键字有序排列,p=SL0.next; p,指示第一个记录的当前位置,for(i=1; in; i+ ),SL1.i-1,记录已按关键字有序，第,i,个记录的当前位置应不小于,i,while(p=1;d=d/2),for(i=1+d;i0&R0.keyaj+1.key,），则将其,交换,，最终达到有序化,2024/11/27,30,起泡排序示例,初始,关键,字,51,33,62,96,87,17,28,51,第,一,趟,33,51,62,87,17,28,51,96,第,四,趟,33,17,28,51,51,62,87,96,第,三,趟,33,51,17,28,51,62,87,96,第,二,趟,33,51,62,17,28,51,87,96,第,五,趟,17,28,33,51,51,62,87,96,第,六,趟,17,28,33,51,51,62,87,96,2024/11/27,31,void BubbleSort(RecType R ,，,int n) ,起泡排序, i = n; i,指示无序序列中最后一个记录的位置,while(i1),LastExchange=1; ,记最后一次交换发生的位置,for(j=1;jRj+1.key),Rj,Rj+1; ,逆序时交换,LastExchange=j,;,if,i=LastExchange;,while,起泡排序算法,2024/11/27,32,起泡排序性能分析,平均时间复杂度：,O(n,2,),2024/11/27,33,一组关键字（,19,01,26,92,87,11,43,87,21,），进行冒泡排序，试列出每一趟排序后的关键字序列,自测题,3,冒泡排序,示例,2024/11/27,34,快速排序,基本思想,：,从排序序列中任选一记录作为,枢轴,（或支点），凡其,关键字小于枢轴的记录均移动至该记录之前，而关键字大于枢轴的记录均移动至该记录之后,。一趟排序后“枢轴”到位，并将序列分成两部分，再分别对这两部分排序。,由,Hoare,(,图灵奖获得者,)1962,年提出，被评为,20,世纪十大优秀算法之一,。,2024/11/27,35,快速排序图示,不大于,不小于,1,n,枢轴,2024/11/27,36,快速排序示例,初始关键字序列,：,51,33 62 96 87 17,28,51,R0=,51,i(,枢轴,) j,j,向前扫描,i j,第一次交换之后：,28 33,62,96 87 17 ,51,i j,i,向后扫描,i j,第二次交换之后：,28 33 96 87,17,62,51,i j,j,向前扫描,i,j,第三次交换之后：,28 33 17,96,87 62,51,i,向后扫描,i j,第四次交换之后：,28 33 17 87 96 62,51,j,向前扫描,i j,完成一趟排序：,28 33 17,51,87 96 62,51,ij,2024/11/27,37,快速排序示例,初始关键字序列,：,51 33 62 96 87 17 28,51,一趟排序之后,：,28 33 17,51,87 96 62,51,分别进行快速排序：,17,28,33,结束 结束,51,62,87,96,51,62,结束,结束,快速排序后的序列：,17 28 33 51,51,62 87 96,2024/11/27,38,快速排序算法,int Partition(RecType R ,，,int l,，,int h),交换记录子序列,Rl.h,中的记录，使枢轴记录到位并返回其所在位置,int i=l; j=h; ,用变量,i,j,记录待排序记录首尾位置,R0 = Ri;,以子表的第一个记录作枢轴，将其暂存到记录,R0,中,x = Ri.key; ,用变量,x,存放枢轴记录的关键字,while(ij) ,从表的两端交替地向中间扫描,while(i=x) j-;,Ri = Rj; ,将比枢轴小的记录移到低端,while(ij ,Rj = Ri; ,将比枢轴大的记录移到高端,while,Ri = R0;,枢轴记录到位,return i; ,返回枢轴位置,Partition,2024/11/27,39,快速排序算法,void QuickSort(RecType R ,，,int s,，,int t),对记录序列,Rs.t,进行快速排序,if(st),k=Partition(R,s,t);,QuickSort(R,s,k-1);,QuickSort(R,k+1,t);,if,QuickSort,快速排序的,平均时间复杂度,为,O,（,nlog,2,n,）,最差为,O(n,2,),2024/11/27,40,对下列一组关键字（,46,58,15,45,90,18,10,62,）试写出快速排序的每一趟的排序结果,自测题,4,快速排序,示例,2024/11/27,41,设有顺序放置的,n,个桶，每个桶中装有一粒砾石，每粒砾石的颜色是红、白、蓝之一。要求重新安排，使得红色砾石在前，白色砾石居中，蓝色砾石居后。对每粒砾石的颜色只能察看一次，且只允许交换操作来调整砾石的位置。,【,上海大学,1999,二,2(18,分,)】,算法举例,10.1,快速排序,2024/11/27,42,红、白、兰三色排序算法,void QkSort(rectype r ,int n),int i=1, j=1, k=n;,while(j=k),if(,rj=1,) ,当前元素是红色,ri,rj; i+; j+; ,else if(,rj=2,) j+; ,当前元素是白色,else (rj=3,当前元素是兰色,rj,rk; k-; ,QkSort,2024/11/27,43,冒泡排序算法是把大的元素向上移,(,气泡的上浮,),，也可以把小的元素向下移,(,气泡的下沉,),请给出上浮和下沉过程交替的冒泡排序算法。,【,吉林大学,2001,二,.3(9,分,)】【,北京邮电大学,1992,六,(10,分,)】,算法举例,10.2,双向,冒泡排序,2024/11/27,44,void BubbleSort2(int a,int n),相邻两趟向相反方向起泡的冒泡排序算法,change=1;low=0;high=n-1; ,冒泡的上下界,while(lowhigh & change),change=0; ,设不发生交换,for(i=low;iai+1),aiai+1;change=1; ,有交换,修改标志,change,high-; ,修改上界,for(i=high;ilow;i-) ,气泡下沉,小元素上浮,(,向左,),if(aiai-1),aiai-1;change=1; ,有交换,修改标志,change,low+; ,修改下界,while,BubbleSort2,算法举例,10.2,双向,冒泡排序,的算法,2024/11/27,45,对给定关键字序号,j(1jn),，要求在无序记录,A1.n,中找到关键字从小到大排在第,j,位上的记录，写一个算法利用快速排序的划分思想实现上述查找。,(,要求用最少的时间和最少的空间,),例如：给定无序关键字,7,5,1,6,2,8,9,3,，当,j=4,时，找到的关键字应是,5,。,【,中科院研究生院,2003,十二,(15,分,)】【,武汉理工大学,2002,四,.3(35/3,分,)】,算法举例,10.3,快速,排序,2024/11/27,46,int partition(RecType A,int 1,n),int i=1,j=n;x=Ai.key;,i=1;,while(ij),while(i=x) j-;,if(ij) Ai+=Aj;,while(ij ,if(ij) Aj-=Ai;,return i;,void Find_j(RecType A,int n,int j),i=partition (A,1,n);,while(i!=j),if(ij) i=quicksart(A,i+1,n); ,在后半部分继续进行划分,else i=quicksart(R,1,i-1); ,在前半部分继续进行划分,算法举例,10.3,的算法,2024/11/27,47,选择排序,基本思想,：依次从待排序记录序列中选择出关键字值最小（或最大）的记录、关键字值次之的记录、,，并分别将它们定位到序列左侧（或右侧）的第,1,个位置、第,2,个位置、,，从而使待排序的记录序列成为按关键字值由小到大（或由大到小）排列的有序序列。,选择排序种类,：,直接（简单）选择排序,树形选择排序,堆排序,2024/11/27,48,直接选择排序,待排记录序列的状态为：,有序序列,R1.i-1,无序序列,Ri.n,有序序列中,所有记录的关键字均小于无序序列中记录的关键字,，第,i,趟直接选择排序是从无序序列,Ri.n,的,n-i+1,记录中选出,关键字最小,的记录加入有序序列,2024/11/27,49,直接选择排序示例,初始关键字序列,：,51,33 62 96 87,17,28 51, ,第一趟排序后：,17,33,62 96 87 51,28,51, ,第二趟排序后：,17,28,62,96 87 51,33,51, ,第三趟排序后：,17,28,33,96 87 51 62 51,第四趟排序后：,17,28,33,51,87 96 62 51,第五趟排序后：,17,28,33,51,51,96 62 87,第六趟排序后：,17,28,33,51,51,62,96 87,第七趟排序后：,17,28,33,51,51,62,87,96,2024/11/27,50,直接选择排序算法,void SelectSort(RecType R,，,int n), ,对记录序列,R1.n,作直接选择排序。,for(i=1; in; i+) ,选择第,i,小的记录，并交换到位,k=i; ,假定第,i,个元素的关键字最小,for(j=i+1;j=n;j+) ,找最小元素的下标,If(Rj.keyRk.key) k=j;,if(i!=k) RiRk; ,与第,i,个记录交换,for,SelectSort,直接选择排序的,平均时间复杂度,为,O,（,n,2,）,记录移动次数,最好情况,：,0,最坏情况,：3(,n-1),比较次数,(,与初始状态无关,):,2024/11/27,51,基本思想：对,n,个待排序记录的关键字进行两两比较，从中选出,n/2,个较小者再两两比较，直到选出关键字最小的记录为止，此为,一趟排序,。,一趟选出的关键字最小的记录称为“冠军”，而,“亚军”是从与“冠军”比较失败的记录中找出,。,输出“冠军”后，将（冠军）叶子结点关键字改为最大，继续进行锦标赛排序，直到选出关键字次小的记录为止，如此循环直到输出全部有序序列。,树形选择排序(锦标赛排序 ),2024/11/27,52,对关键字序列,72,73,71,23,94,16,05,68,进行树形选择排序,树形选择排序(锦标赛排序 ),05,23,05,72,23,16,05,72,73,71,23,94,16,05,68,冠军,2024/11/27,53,“亚军”是从与“冠军”比较失败的记录中找出的,树形选择排序(锦标赛排序 ),16,23,16,71,23,16,68,72,73,71,23,94,16,68,亚军,2024/11/27,54,n,个记录的锦标赛排序，每选择一个记录需,log,2,n,次比较，,时间复杂度为,O(nlog,2,n),。,缺点：需要,较多的辅助存储空间,；,与“最大值”进行多次多余的比较,。,对树形排序的改进是,堆排序,树形选择排序性能分析,2024/11/27,55,堆的定义：堆是满足下列性质的序列,K,1,K,2, K,n,：,堆排序,或,（,i =1,2,n/2,）,若上述序列是堆，则,K,1,必是序列中的最小值或最大值，分别称作小顶堆或大顶堆,（小堆或大堆，小根堆或大根堆）。,若将此序列看成是一棵完全二叉树，则堆或是空树或是满足下列特性的完全二叉树：其左、右子树分别是堆，任何一个结点的值不大于,(,或不小于,),左,/,右子女结点（若存在）的值,2024/11/27,56,堆排序示例,96,，,51,，,87,，,33,，,28,，,62,，,51,，,17,是大顶堆,例如：,17,，,28,，,51,，,33,，,62,，,96,，,87,，,51,是小顶堆,2024/11/27,57,堆排序,基本思想,：先建一个堆，即先选得一个,关键字最大或最小的记录,，然后与序列中最后一个记录交换，之后将序列中,前,n,-,1,个,记录重新调整为一个堆（调堆的过程称为“筛选”），再将堆顶记录和第,n,-,1,个记录交换，如此反复直至排序结束。,堆排序需解决的两个问题：,如何由一个无序序列建成一个堆？,如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？,2024/11/27,58,第二个问题解决方法,方法：输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直至叶子结点，将得到新的堆,第一个问题解决方法,方法：把整个数组,R1,到,Rn,调整为一个大根堆，即把完全二叉树中以每一个结点为根的子树都调整为堆。需要将以序号为,n/2,， ,n/2,1,，,，,1,的结点作为根的子树调整为堆,用筛选法调整堆,2024/11/27,59,调整堆示例,28,51,33,62,87,96,17,51,(a),堆,28,51,33,62,87,96,51,17,(b)17,与,51,交换后的情景,2024/11/27,60,调整堆示例,51,51,87,62,28,96,33,17,(d)28,与,87,交换后调成的新堆,33,51,51,62,87,96,28,17,(c),调整后的新堆,2024/11/27,61,建堆示例,初始关键字序列：,51,，,33,，,62,，,96,，,87,，,17,，,28,，,51,为例，其初始建大顶堆过程,33,62,96,87,28,17,51,51,(a)4,.,8,是堆，不调整,33,62,96,87,28,17,51,51,(b)3,.,8,是堆，不调整,2024/11/27,62,建堆示例,33,62,96,87,28,17,51,51,(c)2,.,8,不是堆，进行筛选,96,62,51,87,28,17,51,33,(d)1,.,8,不是堆，进行筛选,87,62,51,51,28,17,96,33,(e),建成的大顶堆,2024/11/27,63,堆排序筛选算法,void Sift(RecType R,，,int i,，,int m), ,假设,Ri+1.m,中各元素满足堆的定义，本算法调整,Ri,使序列,Ri.m,中各元素满足堆的性质,R0=Ri;,暂存,for(j=2*i; j=m; j*=2),if(jm ,沿大者（右）方向筛选,if(R0.key0;i-) ,把,R1.n,建成大顶堆,Sift(R,i,n);,for(i=n;i1;i-) ,输出并调堆,R1Ri;,Sift(R,1,i-1); ,将,R1.i-1,重新调整为大顶堆,for,HeapSort,堆排序的,时间复杂度,为,O,（,nlog,2,n,）,2024/11/27,65,时间复杂度：最坏情况下,T(n)=,O(nlogn,),建初始堆时间,：,调用,SIFT,过程,n/2,次，每次以,Ri,为根的子树调整为堆。具有,n,个结点的完全二叉树深度是,h= ,logn,+1 ,第,i,层结点个数至多为,2,i-1,。,SIFT,对深度为,k,的完全二叉树进行比较的关键字次数至多为,2(k-1),，,因此比较总次数不超过,C,1,(n),2,i-1,*2(h-1),=2,h-1,+2,h-2,*2+2,h-3,*3+,+2*(h-1)=2*2,(log,2,n)+1,=4n,重新建堆时间：,排序过程中重新建堆比较总次数不超过,C,2,(n)=2*(,log,n-1,+ ,log,n-2,+,+ ,log,2,)=1;i=i/2),if,(R0.keyRi.key),Rj=Ri; j=i;,else,break,;,Rj=R0;,s,if,t,(2),void,HeapBuilder(RecType R,int,n),for,(i=2;i=n;i+) s,if,t (R,i); ,2024/11/27,70,归并排序,基本思想,：,将具有,n,个待排序记录的序列看成是,n,个长度为,1,的有序序列，进行两两归并，得到,n/2,个长度为,2,的有序序列，再进行两两归并，得到,n/4,个长度为,4,的有序序列，如此重复，直至得到一个长度为,n,的有序序列为止,2024/11/27,71,归并排序示例,二趟归并排序后,：,33 51 62 96,1,7 28,87,初始关键字序列,：,51,33,62,96,87,17,28,一趟归并排序后,：,33 51,62 96,1,7 87,28,三趟归并排序后,：,17,28 33 51 62,87 96,2024/11/27,72,一趟归并排序算法,void Merge(RecType R,RecType R1,int i,int,l,int h),将有序的,Ri.,l,和,R,l,+1.h,归并为有序的,R1i.h,for(j=,l,+1,k=i; i=,l,k+),R,中记录由小到大地并入,R1,if(Ri.key=Rj.key) R1k=Ri+;,else R1k=Rj+;,if(i=,l,) R1k.h=Ri.,l,;,将剩余的,Ri.,l,复制到,R1,if(j=h) R1k.h=Rj.h;,将剩余的,Rj.h,复制到,R1,Merge,2024/11/27,73,归并排序算法,void Msort(RecType R ,RecType R1 ,int s,int t), ,将,Rs.t,进行,2-,路归并排序为,R1s.t,if(s=t) R1s=Rs;,else, m=(s+t)/2; ,将,Rs.t,平分为,Rs.m,和,Rm+1.t,Msort(R,R2,s,m);,递归地将,Rs.m,归并为有序的,R2s.m,Msort(R,R2,m+1,t);,递归地,Rm+1.t,归并为有序的,R2m+1.t,Merge(R2,R1,s,m,t);,将,R2s.m,和,R2m+1.t,归并到,R1s.t,if,MSort,2024/11/27,74,归并排序算法,void MergeSort(RecType R,int n), ,对记录序列,R1.n,作,2-,路归并排序。,MSort(R,R,1,n);,MergeSort,归并排序的设计复杂度为,O(nlogn),2024/11/27,75,自测题,10.,若数据元素序列,11,12,13,7,8,9,23,4,5,是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是,A.,起泡排序,B.,插入排序,C.,选择排序,D.,二路归并排序,【,2009,年全国硕士研究生入学计算机学科专业基础综合试题,】,2024/11/27,76,分配排序,基本思想,：利用关键字的结构，通过“分配”和“收集”的办法来实现排序,分配排序可分为,桶排序,和,基数排序,两类,2024/11/27,77,桶排序,桶排序,（,Bucket Sort,）也称箱排序（,Bin Sort,），其,基本思想,是：设置若干个桶，依次扫描待排序记录,R1,.,n,，把关键字等于,k,的记录全部都装到第,k,个桶里（分配），然后，按序号依次将各非空的桶首尾连接起来（收集）。,2024/11/27,78,基数排序,基数排序,就是一种借助“多关键字排序”的思想来实现“单关键字排序”的算法,假设,n,个记录待排序序列, R1, R2, ,，,Rn,，每个记录,Ri,中含有,d,个关键字,(K,i0, K,i1, ,K,id-1,),则称上述记录序列对关键字,(K,i0, K,i1, ,K,id-1,),有序是指：对于序列中任意两个记录,Ri,和,Rj(1ijn),都满足下列,(,词典,),有序关系：,(K,i0, K,i1, ,K,id-1,) (K,j0, K,j1, ,K,jd-1,),其中,K,0,被称为“,最主,”位关键字，,K,d-1,被称为 “,最次,”位关键字。,2024/11/27,79,最高位优先,MSD,法：先对,K,0,进行排序，并按,K,0,的不同值将记录序列分成若干子序列之后，分别对,K,1,进行排序，,，依次类推，直至最后对最次位关键字排序完成为止。,最低位优先,LSD,法：先对,K,d-1,进行排序，然后对,K,d-2,进行排序，依次类推，直至对最主位关键字,K,0,排序完成为止。排序过程中不需要根据“前一个”关键字的排序结果，将记录序列分割成若干个,(“,前一个”关键字不同的,),子序列。,实现多关键字排序通常有两种作法,:,2024/11/27,80,基数排序示例,p,369,367,167,239,237,138,230,139,第一次分配得到：,B0,.,f230B0,.,e,B7,.,f367167237B7,.,e,B8,.,f138B8,.,e,B9,.,f369239139B9,.,e,第一次收集得到：,p230367167237138369239139,2024/11/27,81,基数排序示例,第二次分配得到：,B3,.,f230237138239139B3,.,e,B6,.,f367167369B6,.,e,第二次收集得到：,p230237138239139367167369,2024/11/27,82,基数排序示例,第三次分配得到：,B1,.,f138139167B1,.,e,B2,.,f230237239B2,.,e,B3,.,f367369B3,.,e,第三次收集之后便得到记录的有序序列：,p,138,139,167,230,237,239,367,369,2024/11/27,83,基数排序的类型定义,#define n,待排序记录的个数,typedef struct,int keyd; ,关键字由,d,个分量组成,int next; ,静态链域,AnyType other; ,记录其他数据域,SLRecType;,SLRecType Rn+1; R1.n,存放,n,个待排序记录,typedef struct,int f,e; ,队列的头、尾指针,SLQueue;,SLQueue Bm ,用队列表示桶，共,m,个,2024/11/27,84,基数排序的算法,int RadixSort(SLRecType R, int n), ,对,R1.n,进行基数排序，返回收集用的链头指针,for(i=1;i=0;j-) ,进行,d,趟排序,for(i=0;im;i+) ,初始化桶, Bi.f=-1; Bi.e=-1; for,while(p!=-1) ,一趟分配，,按关键字的第,j,个分量进行分配,k=Rp.keyj; k,为桶的序号,if(Bk.f=-1) Bk