数据库——排序.ppt

,*,第十章 排序,10.1,基本概念,10.2,插入排序,10.3,交换排序,10.4,选择排序,10.5,归并排序,10.6,基数排序,10.7,内部排序的比较,10.8,外部排序,10.9,小 结,第十章 排序,1,本章主要内容,本章主要内容，本章详细介绍了排序的基本概念和常见的排序方法，包括常用的内部排序方法，外部排序方法等内容。通过本章的学习，应掌握如下内容：,l,插入排序,l,交换排序,l,选择排序,l,归并排序,l,基数排序,l,外部排序,l,各种排序的比较,2,关键字,：在排序过程中，所依据的数据项称为“关键字”，也称为排序记录的关键码。,排序,：对任意排列的数据元素序列，通过某种算法使其满足按关键字递增（或递减）关系的过程。,排序的稳定性和不稳定性,：对需要排序的数据元素序列，将其按关键字进行排序，若相同关键字元素之间的位置关系，排序前与排序后的相对位置不发生变化，称此排序方法满足,稳定性,；否则称这种排序方法满足,不稳定性,。,10.1,基本概念,3,排序算法中结点的数据类型描述方法：,typedef,int,KeyType,;,typedef,struct,KeyType,key;,ElemType,;,typedef,struct,ElemType,dataMAXSIZE+1,；,/*,结点数组*,/,int,length,；,/*,表长度*,/,SL,；,内部排序和外部排序,：,内排序是指待排序列完全存放在内存中所进行的排序过程，适合记录较少的序列。如果待排序列记录数量非常多，排序过程不能一次在内存中完成，必需对外存储器进行访问，这样的排序称为,外部排序,。,4,10.2.1,直接插入排序,直接插入排序：,是指将一个记录按关键字大小的顺序插入到有序序列中的过程。,排序过程如下：,设有一组关键字,key,1,key,2,key,n,;,认为,key,1,就是一个有序序列,;,令关键字为,key,2,的数据元素插入到上述表长为,1,的有序序列中,使之成为一个表长为,2,的有序序列,;,最后让关键字为,key,n,的数据元素插入到上述表长为,n-1,的有序序列中,使之成为一个表长为,n,的有序序列。,5,【,算法,10.1】,直接插入排序,void,InsertSort,(SL *p),for(i=2,；,ilength,；,i+),if(p-datai.keydatai-1.key),p-data0=p-datai,；,/*,设置监视哨*,/,for(j=i-1,；,p-data0.keydataj.key,；,j-),p-dataj+1=p-dataj,；,/*,记录后移*,/,p-dataj+1=p-data0,；,/*,插入到正确位置*,/,/*if*/,a0 a1 a2 a3 a4 a5,i=1,：,6 13 9 26 11,i=2,：,6 13 9 26 11,6,【,例,10-1】,有一个待排序列,6,，,13,，,9,，,26,，,11,，将其按照直接插入方法实现排序。如图所示：,初始关键字：,a1 a2 a3 a4 a5,i=1,：,6 13 9 26 11,i=2,：,6 13 9 26 11,i=3,：,6 9 13 26 11,i=4,：,6 9 13 26 11,i=5,：,6 9 11 13 26,7,算法分析：,空间复杂度,：该算法只使用了一个辅助存储单元,p-data0,，,所以是,O(1),；,时间复杂度,：向有序表中逐个插入记录的操作，进行了,n-1,趟，每一趟比较和移动记录的次数取决于待排序列按关键码的初始排列状态。,最好情况下,，即初始序列已经有序的情况下，比较,n-1,次，移动,2(n-1),次。,最坏情况下,，即初始序列在呈逆序的情况下，比较,n(n-1)/2,次，移动,n(n-1)/2+2n,次。,因此，时间复杂度为,O(n,2,),，,排序方法稳定,，适合于记录个数比较少的情况，若原始数据序列在基本有序的情况下，算法效率比较高。,8,直接插入排序算法中，数据的移动是一步步进行的，当数据量很大时，比较和移动的次数都非常大。,希尔排序,是对该算法的改进。,希尔排序基本思想,是先将整个待排序列分割成若干个子序列，然后对各子序列分别进行直接插入排序，当达到有序状态时，再进行一次直接插入排序。,排序过程如下,：每趟排序，根据对应的步长，将待排序列分割成若干长度为,m,的子序列，分别对各子序列进行直接插入排序,;,缩小步长,再继续划分子序列,排序，直到步长为,1,为止。,10.2.2,希尔排序,9,【,例,10-2】,待排序列为,34,，,81,，,72,，,42,，,10,，,28,，,52,，,77,，,33,，,13,，,109,，,4,，,42,，,89,。,步长因子,d,i,分别取,5,、,3,、,1,，则排序过程如下：,d,0,=5,34,81,72,42,10,28,52,77,33,13,109,4,42,89,子序列分别为,34,，,28,，,109,，,81,，,52,，,4,，,72,，,77,，,42,，,42,，,33,，,89,，,10,，,13,。,10,第一趟排序结果：,28,4,42,33,10,34,52,72,42,13,109,81,77,89,第二趟排序结果：,13 4 34 28 13,42,33 72 42 52 89 81 77 109,此时，序列基本“有序”，对其进行直接插入排序，得到最终结果：,4 10 13 28 33 34,42,42,52 72 77 81 89 109,11,【,算法,10.2】,希尔排序,void,ShellInsert(SL,*p,，,int,dk,),/*,一趟增量为,dk,的插入排序，,dk,为步长因子,*,/,for(i=dk+1,；,ilength,；,i+),if(p-datai.key,datai-dk.key,),p-data0=p-datai,；,for(j=,i-dk,；,j0&p-data0.key dataj.key,；,j=,j-dk,),p-,dataj+dk,=p-dataj,；,p-,dataj+dk,=p-data0,；,12,算法分析,:,算法中的循环是针对一个特定增量,d,i,进行分组插入排序，同一组记录的关键字进行比较，需要调整位置时，关键字较小的记录是按照,d,i,的宽度进行移动的，当,d,i,=1,时，此算法就是直接插入方法。,有人曾在大量实验基础上推算出，它的,时间复杂度为,O(n,3/2,),。,空间复杂度为,O(1),。,排序方法不稳定,。,步长因子序列的选取：步长因子比较常用的选择,d,0,为,n/2,，,d,1,为,n/4,，,di,=1,（,n,为表的长度），一般不选择,2,的整数次幂，但是排序最后最后步长必须是,1,。,13,基本思想：,对待排序列中相邻元素进行比较，如果为逆序,，,则将这两个元素的位置交换。重复此操作直到整个序列全部有序为止。,10.3.1,冒泡排序,基本思路为：首先将第一个记录的关键字和第二个记录的关键字比较，若为逆序，则两个记录交换；然后比较第二个记录和第三个记录的关键字，,，,直至第,n-1,个记录和第,n,个记录的关键字比较、交换结束为止。经过第一趟排序后，关键字最大,(,或最小,),的记录被调整到最后一个记录的位置。下一趟排序时，这个关键字最大,(,或最小,),的记录就不必考虑了。直到某一趟排序过程中没有进行交换操作为止。,10.3,交换排序,14,【,算法,10.3】,冒泡排序,void bubble(SL*p),n=p-length;,for(i=1;ii;j+),if(p-dataj.keydataj-1.key),p-data0=p-dataj;p-dataj=p-dataj-1;,p-dataj-1=p-data0;flag=1;,if(flag,=0),printf,(“,排序结束”,);break;,/*bubble*/,15,算法分析,:,算法中,flag,为标志变量，当某一趟排序中进行过记录交换时,flag,的值为,1,，否则为,0,。所以外循环结束条件是：,flag=0,，,已有序，或,i=n,。,空间复杂度：,仅用一个辅助单元,复杂度为,O(1),。,时间复杂度：,冒泡排序中元素之间比较的次数为,n(n-1)/2,。,若所给的序列是满足排序要求，则元素移动的次数为,0(,最好情况,),；若所给的序列是正好成逆序状态，元素移动的次数为,3n(n-1)/2(,最坏情况,),。其平均时间复杂度为,O(n,2,),。,16,当冒泡排序在数据元素的关键字呈逆序时进行排序，需要进行多次比较和移动操作，数据元素移动是一步一步进行的，且有很多是重复的。快速排序是对冒泡排序算法的改进。,基本思想,：快速排序又称为分区交换法，是通过对某关键字,(,支点,),的比较，将各待排序列分成前后两部分，后半部分所有记录的关键字值大于等于支点的关键字值，前半部分所有记录的关键字小于等于支点的关键字值。将待排序列按关键字以支点分成两部分的过程，称为,一次划分,。对各部分不断的划分，直到整个序列按关键字有序为止。,10.3.2,快速排序,17,【,例,10-3】,一趟快速排序过程示例,r0 r1 r2 r3 r4 r5 r6 r7 r8 r9 r10,43 28 39 76 98 69 4 51 58,28,r0 r1 r2 r3 r4 r5 r6 r7 r8 r9 r10,43 43 28 39 76 98 69 4 51 58,28,low,high,从,high,向前搜索小于,r0.key,的记录，将其赋值给,low,指向的位置,r0 r1 r2 r3 r4 r5 r6 r7 r8 r9 r10,43,28,28 39 76 98 69 4 51 58,28,low high,从,low,向后搜索大于,r0.key,的记录，将其赋值给,high,指向的位置,18,43,28,28,39,76,98 69 4 51 58 76,low high,从,high,向前搜索小于,r0.key,的记录，将其赋值给,low,指向的位置,43,28,28,39 4 98 69,4,51 58 76,low high,从,low,向后搜索大于,r0.key,的记录，将其赋值给,high,指向的位置,19,43,28,28,39 4,98,69,98,51 58 76,low high,43,28,28,39 4,98,69 98 51 58 76,low high,low=high,，,划分结束，将,r0.key,的值赋值给,low(high),指向的位置,28,28,39 4,43,69 98 51 58 76,大于等于,43,小于等于,43,20,快速排序的递归过程可用生成一棵二叉树的过程形象地表示，每棵子树的根结点是各次划分时的支点，,28,76,4,39,98,58,43,28,51,69,待排序列对应递归调,用过程的二叉树,r0 r1 r2 r3 r4 r5 r6 r7 r8 r9 r10,43 28 39 76 98 69 4 51 58,28,28,28,39 4,69 98 51 58 76,初始序列,43,69 98 51 58 76,一次划分后,21,算法分析：,时间复杂度,：在,n,个记录的待排序列中，一次划分需要约,n,次关键码比较,。,若每次划分的前后两部分数据元素个数基本相等，则需要经过,log,2,n,次划分，所以算法时间复杂度为,nlog,2,n,，,最坏情况下，时间复杂度为,O(n,2,),。,空间复杂度,：快速排序是递归的，每层递归调用的指针和参数均要用栈来存放，递归调用次数与二叉树的深度一致。存储开销在理想情况下为,O(log,2,n),，,即树的高度；在最坏情况下，二叉树是一个单支，这时算法的空间复杂度为为,O(n),。,22,是以降低数据元素的移动次数为排序思路。,10.4.1,直接选择排序,排序过程,：,第一次，选取整个序列中关键字最小的记录与第一个元素交换；,第二次，从剩余的,n-1,个记录中选出关键字最小的记录与第二个记录交换；,第,i,次，则从剩余的,n-i+1,个记录选出关键字最小的记录与第,i,个记录交换；,直到整个序列按关键码有序。,10.4,选择排序,23,【,例,10-4】,待排序列,35 28 45 55 19 68,初始状态,35,28 45 55,19,68,i=1 ,19,28,45 55 35 68,元素,19,和,35,交换,i=2 ,19 28,45,55,35,68,元素,35,和,45,交换,i=3 ,19 28 35,55,45,68,元素,45,和,55,交换,i=4 ,18 24 35,45,55,68,i=5 ,18 24 35 45 55,68,i=6 ,18 24 35 45 55 68,24,【,算法,10.5】,直接选择排序,void,SelectSort(SL,*p),for(i=1,；,ilength,；,i+),k=i;,for(j=i+1,，,k=i,；,jlength,；,j+),if(p-datak.keyp-dataj.key),k=j,；,/*t,中存放关键码最小记录的下标*,/,if(i!=k),/*,关键码最小的记录与第,i,个记录交换*,/,p-data0=p-datai,；,p-datai=p-datak,；,p-datak=p-data0;,25,算法分析：,空间复杂度,：一个附加单元的存储空间，所以是,O(1),。,时间复杂度,：该算法使用了循环的嵌套形式，复杂度为,n(n+1)/2,，,所以为,O(n,2,),。,算法是,稳定,的。,直接选择排序中比较的次数比较多。,10.4.2,堆排序,(Heap Sort),堆排序就是直接选择排序算法的改进算法。,堆的定义,：设有,n,个元素的序列,R,1,R,2,R,n,其关键字为,k,1,，,k,2,，,，,k,n,，,当且仅当满足下述关系之一时，称之为堆,.,26,32,29,87,48,57,34,14,93,小根堆,48,87,29,32,34,57,93,14,大根堆,6,29,87,48,57,10,14,93,非堆,下面讨论小根堆,27,堆排序大体分,两步处理,：,第一步建立堆结构,。先取,i=n/2,（,i,是第,n,个结点的双亲的编号），将以,i,结点为根的子树调整为堆；然后令,i=i-1,；,再将以,i,结点为根的子树调整成为堆。直到,i=1,为止，初建堆完成。,第二步堆排序,。首先输出堆顶元素，让堆中最后一个元素上移到堆顶位置，然后恢复堆，重复执行输出堆顶元素、堆尾元素移到堆顶和恢复堆的操作，直到全部元素输出完为止。,因此，实现堆排序需解决两个问题：,1.,如何将,n,个元素的序列按关键码建成堆；,2.,输出堆顶元素后，调整剩余元素成为一个新堆。,28,【,例,10-6】,设有,8,个记录的关键字是,53,，,36,，,30,，,91,，,47,，,12,，,24,，,85,，试用堆排序的方法，将这组记录由小到大排序。,第一步,：建立堆结构，其过程如图所示。,36,30,91,47,24,12,53,85,8,个结点初始状态,36,30,91,47,24,12,53,85,从第,4,个结点开始筛选,29,91,36,12,85,47,24,30,53,第,2,个结点为根的,子树已是堆,36,12,85,47,24,30,53,91,对整棵树进行筛选,36,53,85,47,24,30,12,91,36,30,85,47,24,12,53,91,对第,3,个结点开始筛选,30,第二步,：堆排序。这是反复输出堆顶元素，将堆尾元素上移至堆顶，再调整恢复堆的过程，恢复堆的过程与初建堆中,i=1,时所进行的调整操作相同。,输出,12,，将,91,送入堆顶，调整恢复堆,36,24,85,47,53,30,12,91,30,36,85,47,24,53,91,31,53,36,85,47,91,输出,30,，将,91,送入堆顶，调整恢复堆,53,47,85,91,36,输出,24,，将,53,送入堆顶，调整恢复堆,36,30,85,47,91,53,53,36,85,47,30,91,32,85,91,输出,53,，,将,91,送入堆顶,91,85,53,47,85,91,输出,36,，将,91,送入堆顶，调整恢复堆,53,85,91,47,53,85,91,输出,47,，将,91,送入堆顶，,调整恢复堆,91,85,53,33,归并的含义是将两个或两,个以上的有序序列归并成一个新的有序表,。归并排序可分为多路归并排序和两路归并排序。它既可以用于,内部排序,，也可以用于,外部排序,。,一趟两路归并算法的思想（以升序为例）：先用两个指针分别指向两个序列的第一个数据元素，进行比较，取出较小者，然后将其所在序列的指针后移，重复以上过程，直到指针达到序列的末尾，这时将另一个序列的剩余元素依次顺序放到有序序列的后面即可。,10.5,归并排序,34,将两个有序序列,L-datat.m,和,L-datam+1.n,归并为有序序列,L1-t.n,的过程：,i=t,；,j=m,；,k=t,；,若,im,或,jn,，,执行；,比较,L-datai,和,L-dataj,关键字,将,较小的存入,L1,中,:,如果,L-datai.keydataj.key,；,L1-datak=L-datai,；,i+,；,k+,；,执行；,否则,，,L1-datak=L-dataj;j+;k+;,执行；,将尚未处理完的子表中元素存入,L1,；,如果,idataim,存入,L1-datakn,；,如果,jjn,存入,L1-datakn,；,合并结束。,35,【,算法,9.7】,一趟两路归并排序,void Merge(SL *L,SL *L1,，,int,t,，,int,m,，,int,n),for(i=t,，,j=m,，,k=t,；,i=m&jdatai.keydataj.key),L1-datak=L-datai,；,i+,；,else L1-datak=L-dataj,；,j+,；,/*for*/,if(idatakn=L1-dataim-1,；,if(jdatakn=L1-datajn,；,/*Merge*/,36,【,例,10-7】,有一个序列,12,，,9,，,44,，,10,，,99,，,61,，,65,，,43,，,76,，其两路归并算法的过程：,初始关键字,12,9,44,10,99 ,61,65,43,76,一趟归并后,9 12,10 44,61 99 ,43 65,76,二趟归并后,9 10 12 44,43 61 65 99,76,三趟归并后,9 10 12 43 44 61 65 99,76,四趟归并后,9 10 12 43 44 61 65 76 99 ,37,两路归并排序思想：把序列所含的,n,个记录看作,n,个有序的子序列，然后两两归并，得,n/2,个长度为,2,或,1,的有序子序列；再两两归并，以此类推直到得到的子序列长度为,n,，,排序完毕。,算法分析,：,空间复杂度,为,O(n),。,时间复杂度,：对包含,n,个数据元素的表，将这,n,个数据元素看作叶子结点，若将两两归并生成的子表看作它们的父结点，则归并过程对应由叶子结点向根结点生成一棵二叉树的过程。所以归并趟数约等于二叉树的高度,-1,，即,log,2,n,，,每趟归并需移动记录,n,次，故为,O(nlog,2,n),。,38,是一种借助于多关键码排序的思想，将单关键码按基数分成“多关键码”进行排序的方法。,多关键字排序的基本过程是首先根据多个关键字分别排序，最后再将其合并到一起。,【,例,10-8】,扑克牌中,52,张牌，可按花色和面值分成两个字段，其大小关系为：,花色,：方块,梅花,红心,黑心,面值：,2345678 9 10 J Q K A,若对扑克牌按花色、面值进行升序排序，得到如下序列,:,方块,2,3,.,A,，,梅花,2,3,.,A,，,红心,2,3,.,A,，,黑心,2,3,.,A,10.6,基数排序,39,本节假设记录的关键字为整型。,最低位优先法,：即是首先根据关键字最低位,(,个位,),有效数字进行排序，然后根据次低位,(,十位,),有效数字进行排序，以此类推，直到根据最高位有效数字进行排序，产生一个有序序列。,假设有,n,个记录，其关键字在,0999,之间，每位上有效数字在,09,之间共有,10,种可能性，则基数为,10,，在进行“,分配,”操作时涉及,10,个队列，即队列的个数与基数相同。此处关键字最多位数是,3,，那么需要进行,3,趟“,分配”和“收集,”操作。,40,248,279,585,134,549,970,043,018,159,053,初始记录的静态链表,第一趟按个位数分配，修改结点指针域，将链表中的记录分配到相应链队列中,e0 e1 e2 e3 e4 e5 e6 e7 e8 e9,f0 f1 f2 f 3 f4 f5 f6 f7 f8 f9,134,585,970,54,9,15,9,27,9,043,053,24,8,01,8,【,例,10-9】,对序列,248,，,159,，,43,，,970,，,549,，,134,，,585,，,279,，,18,，,53,进行基数排序。,41,970,159,018,248,585,134,053,549,043,279,(c),第一趟收集：将各队列链接起来，形成单链表,e0 e1 e2 e3 e4 e5 e6 e 7 e8 e9,f0 f1 f2 f3 f4 f5 f6 f7 f8 f9,(d),第二趟按十位数分配，修改结点指针域，将链表中的记录分配到相应链队列中,1,3,4,0,1,8,585,1,5,9,0,5,3,970,279,2,4,8,0,4,3,5,4,9,42,018,970,159,053,549,248,043,279,134,585,(e),第二趟收集：将各队列链接起来，形成单链表,(f),第三趟按百位数分配，修改结点指针域，将链表中的记录分配到相应链队列中,e0 e1 e2 e3 e4 e5 e6 e7 e8 e9,0,43,0,18,0,53,134,159,248,279,9,70,f0 f1 f2 f3 f4 f5 f6 f7 f8 f9,549,585,018,549,279,248,159,134,053,5859,043,970,(g),第三趟收集：各队列链接起来，形成单链表。此时序列已有序,43,算法思路如下：,第一趟“分配”，根据关键字个位有效数字，把所有记录分配到相应的,10,个队列中去。,f0,，,e0,表示,0,号队列的头、尾指针；,f9,，,e9,表示,9,号队列的头、尾指针；例如：关键字,549,的记录被分配到,9,号队列。,第一趟收集，把所有非空队列按队列号由小到大的顺序将关键字出队。此序列关键字的个位已经有序；高位仍处于无序状态。,以后各他趟，分别根据关键字的十位、百位有效数字重复类似第、步的“分配”与“收集”操作，最终将得到一个按照关键字由小到大的序列。,44,第一趟“分配”，根据关键字个位有效数字，把所有记录分配到相应的,10,个队列中去。,f0,，,e0,表示,0,号队列的头、尾指针；,f9,，,e9,表示,9,号队列的头、尾指针；例如：关键字,549,的记录被分配到,9,号队列。,第一趟收集，把所有非空队列按队列号由小到大的顺序将关键字出队。此序列关键字的个位已经有序；高位仍处于无序状态。,以后各他趟，分别根据关键字的十位、百位有效数字重复类似第、步的“分配”与“收集”操作，最终将得到一个按照关键字由小到大的序列。,45,算法分析,：,时间复杂度：设待排序列含,n,个记录，,d,个关键码，关键码的基数为,radix,，,则进行链式基数排序的时间复杂度为,O(d(n+radix),，,其中，一趟分配时间复杂度为,O(n),，,一趟收集时间复杂度为,O(radix),，,共进行,d,趟分配和收集。,综合比较上述讨论的各种内部排序方法，其性能指标如表,9-1,所示。通常从下面二方面衡量排序方法的性能，一方面数据排序期间的运算量，一般考虑关键字的比较次数和记录的平均移动次数；另一方面，数据排序期间所需要的辅助存储空间。,46,排序方法,时间复杂度,特殊情况,空间复杂度,算法稳定性,直接插入,O(n,2,),原表有序,O(n),O(1),稳定,直接选择,O(n,2,),O(n,2,),O(1),不稳定,冒泡排序,O(n,2,),原表有序,O(n),O(1),稳定,希尔排序,O(n,1.3,),/,O(1),不稳定,快速排序,O(nlog,2,n),原表有序,O(n,2,),O(nlog,2,n),不稳定,堆排序,O(nlog,2,n),O(nlog,2,n),O(1),不稳定,两路归并,O(nlog,2,n),O(nlog,2,n),O(n),稳定,基数排序,O(d(n+radix),O(d(n+radix),O(radix),稳定,10.7,内部排序的比较,47,在应用中，应根据不同情况、不同要求选择较合适的方法，甚至可将多种方法结合使用。下面几点建议，仅供读者参考。,(1),当待排序的记录数,n,不大时,(,约,n50),，,可选用表中前三种排序方法。它们的时间复杂度虽为,O(n,2,),，,但方法简单，容易实现。,(2),当,n,值很大，不强求排序稳定性，并且内存容量不宽余时，应选用快速排序或堆排序。一般来讲，他们排序速度非常快。,(3),当,n,值很大，对排序稳定性有要求，并内存容量宽余时，用归并排序最为合适。,48,10.8.1,外部排序,在对大型文件排序时，由于文件很大，不可能将整个文件的所有记录都同时调入内存中进行排序，就要利用外部排序技术来完成排序。,外部排序方法最常用的是多路归并法。这种方法基本要经过两个步骤：,第一步，按可按内存大小，将外存上含,n,个记录的文件分成若干个长度为,k,的子文件或段,(segment),，,依次读入内存并利用有效的内部排序方法对它们进行排序，并将排序结果重新写入外存。通常称这些有序子文件为归并段或顺串；,10.8,外部排序,49,假设有一个含,10000,个记录的文件，首先通过,10,次内部排序得到,10,个初始归并段,A,1,A,10,，,其中每一段都含,1000,个记录。然后对它们作如图,9-12,所示的两两归并，直至得到一个有序文件为止。,将两个有序段归并成一个有序段的过程，若在内存中进行，前面讨论的两路归并排序中的,Merge,函数便可实现此归并。,第二步，对这些归并段进行逐趟归并，使归并段,(,有序子文件,),逐渐由小到大，最后在外存上形成一个排序文件。,50,一般情况下，外部排序所需总时间,=,内部排序所需时间,mt,is,+,外存信息读写的时间,dt,io,+,内部归并排序所需时间,sut,mg,其中：,t,is,是为得到一个初始归并段进行的内部排序所需时间的均值；,t,io,是进行一次外存读,/,写时间的均值；,ut,mg,是对,u,个记录进行内部归并所需时间；,m,为经过内部排序之后得到的初始归并段的个数；,s,为归并的趟数；,d,为总的读,/,写次数。由此，上例,10000,个记录利用两路归并进行排序所需总的时间为：,10t,is,+500t,io,+410000t,mg,但是，在外部排序中实现两路归并时，不仅要调用,Merge,函数，而且要进行外存的读,/,写，这是由于我们不可能将两个有序段及归并结果同时放在内存中的缘故。对外存上信息的读,/,写是以“物理块”为单位。,51,10.8.2,多路平衡归并的实现,从上式可见，增加,k,可以减少,s,，,从而减少外存读,/,写的次数。但是，从下面的讨论中又可发现，单纯增加,k,将导致增加内部归并的时间,ut,mg,。,那末，如何解决这个矛盾呢？,先看两路归并。,u,个记录分布在两个归并段上，按,Merge,函数进行归并。每得到归并后的含,u,个记录的归并段需进行,u-1,次比较。,再看,k-,路归并。令,u,个记录分布在,k,个归并段上，显然，归并后的第一个记录应是,k,个归并段中关键码最小的记录，即应从每个归并段的第一个记录的相互比较中选出最小者，这需要进行,k-1,次比较。同理，每得到归并后的有序段中的一个记录，都要进行,k-1,次比较。显然，为得到含,u,个记录的归并段需进行,(u-1)(k-1),次比较。,52,因此，对,n,个记录的文件进行外部排序时，在内部归并过程中进行的总的比较次数为,s(k-1)(n-1),。,假设所得初始归并段为,m,个，则可得内部归并过程中进行比较的总的次数为,随,k,增加而增长，则内部归并时间随,k,增加而增长。这将抵消由于增大,k,而减少外存信息读写时间所得效益，这是我们所不希望的。,53,1,深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用。,2,了解各种方法的排序过程及其依据的原则。基于“关键字间的比较”进行排序的方法可以按排序过程所依据的不同原则分为插入排序、交换排序、选择排序、归并排序和基数排序等五类。,3,掌握各种排序方法的时间复杂度的分析方法。能从“关键字间的比较次数”分析排序算法的平均情况和最坏情况的时间性能。按平均时间复杂度划分，内部排序可分为三类：,O(n,2,),的简单排序方法，,O(nlog,2,n),的高效排序方法和,O(d*n),的基数排序方法。,小 结,54,4,理解排序方法“稳定”或“不稳定”的含义，弄清楚在什么情况下要求应用的排序方法必须是稳定的。,55,