第十章排序

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第十章 内部排序,10.1,排序的定义和方法,排序是将无序的记录序列调整为有序记录序列的一种操作。,稳定的排序方法,：,对于两个关键字相等的记录在经过排序之后，不改变它们在排序之前在序列中的相对位置。,不稳定的排序方法：,对于两个关键字相等的记录在经过排序之后，改变了它们在排序之前在序列中的相对位置。,根据在排序过程中涉及的存储器不同，可将排序方法分为两大类：,1,）,内部排序：,在排序进行的过程中不使用计算机外部存储器的排序过程。,2,）,外部排序：,在排序进行的过程中需要对外存进行访问的排序过程。本章仅讨论各种内部排序的方法。,内部排序的过程是一个逐步扩大记录的,“,有序序列,”,区域的长度的过程。大多数排序方法在排序过程中将出现如动画所示,“,有序,”,和,“,无序,”,两个区域 。,演示,10.2,插入排序,插入排序的准则是，在有序序列中插入新的记录以达到扩大有序区的长度的目的。,10.2.1,直接插入排序,一趟直接插入排序的基本思想则是,:,在对记录序列,R1.n,的排序过程中，区段,R1.i-1,中的记录已按关键字非递减的顺序排列，将,Ri,插入到有序序列,R1.i-1,中，使区段,R1.i,中的记录按关键字非递减顺序排列。,演示,实现一趟插入排序的步骤为：,1),在,R1.i-1,中查找,Ri,的插入位置，即确定,j(0j,i),使得,R1.j.keyRi.key,Rj+1.i-1.key,2),将,Rj+1.i-1,中的记录后移一个位置；,3),将,Ri,插入到,j+1,的位置。,算法,10.2,void,InsertSort,(,SqList,&,L),/,对顺序表,L,作直接插入排序,for,( i=2; i=,L.length,; +i ),if,(,L.ri.key, L.ri-1.key ),/,将,L.ri,插入有序子表,L.r0 =,L.ri,;,L.ri,=L.ri-1;,for,( j=i-2; L.r0.key ,L.rj.key,; -j ),L.rj+1 =,L.rj,;,/,记录后移,L.rj+1 = L.r0;,/,插入到正确位置,/ if,/,InsertSort,直接插入排序的时间复杂度：,当待排记录处于,“,正序,”,(,即记录按关键字从小到大的顺序排列,),的情况时，所需进行的关键字比较和记录移动的次数最少（分别为：,n-1,，,0,），反之，当待排记录处于,“,逆序,”,(,即记录按关键字从大到小的顺序排列,),的情况时，所需进行的关键字比较和记录移动的次数最多（分别为： ， ）；,若待排记录序列处于随机状态，则可以最坏和最好的情况的平均值作为插入排序的时间性能的量度。一般情况下，直接插入排序的时,间复杂度为,O,(n,2,),。,10.2.2,折半插入排序,演示,算法,10.3,void,BInsertSort,(,SqList,&,L),/,对顺序表,L,作折半插入排序,for,( i=2; i=,L.length,; +i ),L.r0 =,L.ri,;,/,将,L.ri,暂存到,L.r0,low = 1; high = i-1;,while,(low=high),/,在,rlow.high,中折半查找有序插入的位置,m = (low+high)/2;,/,折半,if,(L.r0.key =low; -j ) L.rj+1 =,L.rj,; /,记录后移,L.rhigh+1 = L.r0;,/,插入,/,BInsertSort,折半插入排序只能减少排序过程中关键字比较的时间，并不能减少记录移动的时间，因此折半插入排序的时间复杂度仍为,O,(n,2,),。,10.2.3 2-,路插入排序,10.2.4,表插入排序,表插入排序是以静态链表作待排记录序列的存储结构实现的插入排序。这个静态链表由存储记录的顺序表和附加的指针数组构成，静态链表中的指针实际上指的是数组的下标。表插入排序分两步进行：首先构造一个有序链表；然后按照,附加指针,的指示将结点中的记录重新排列成一个有序序列。,演示,算法,10.4,void,Arrange (,SqList,&,L,，,int,Next ),/,根据,Next,中的指针值调整记录位置，使得,L,中记录,/,按关键字非递减有序顺序排列,p = Next0;,/ p,指示第一个记录的当前位置,for,( i=1; iL.length-1; +i ),/ SL.r1.i-1,中记录已按关键字有序排列，,/,第,i,个记录 在,L,中的当前位置应不小于,i,while,(pi) p =,Nextp,;,/,找到第,i,个记录，并用,p,指示其在,L,中当前位置,q =,Nextp,;,/ q,指示尚未调整的后继记录,if,( p,!,= i ),L.rpL.ri,;,/,交换记录，使第,i,个记录到位,Nexti, = p; /,指向被移走的记录，使得以后可由,while,循环找回,/ if,p = q;,/ p,指向下一个将要调整的记录,/ for,/ Arrange,容易看出，在重排过程中至多进行,3(n-1),次移动记录，然而整个表插入排序过程也仅仅是减少了移动记录的时间，所以它的时间复杂度仍为,O,(n2),。,10.2.5,希尔排序,希尔排序又称,“,缩小增量排序,”,，它的,基本思想是，先对待排序列进行,“,宏观调整,”,，待序列中的记录,“,基本有序,”,时再进行直接插入排序。,演示,例如一个含,11,个关键字的序列,(16,，,25,，,12,，,30,，,47,，,11,，,23,，,36,，,9,，,18,，,31),的希尔排序过程,演示,算法,10.5,void,ShellInsert,(,SqList,&,L,，,int,dk,),/,对顺序表,L,作一趟增量为,dk,的希尔排序,for,( i=dk+1; i=,L.length,; +i ),if,(,L.ri.key,0,&,L.r0.key ,L.rj.key,; j-=,dk,),L.rj+dk, =,L.rj,;,/,记录后移,L.rj+dk, = L.r0;,/,插入到正确位置,/ if,/,ShellInsert,算法,10.6,void,ShellSort,(,SqList,&,L,int,dlta,int,t),/,按增量序列,dlta0.t-1,对顺序表,L,作希尔排序,for,(k=0; kt; +t),ShellInsert(L,dltak,);,/,一趟增量为,dltak,的插入排序,/,ShellSort,希尔排序的时间复杂度和所取增量序列相关，例如已有学者证明，当增量序列为,2,t-k-1,(k=0,1, ,，,t-1),时，希尔排序的时间复杂度为,O,(n,3/2,),。,10.3,快速排序,10.3.1,起泡排序,演示,演示,在待排记录处于,“,正序,”,时取最小值，此时只需进行一趟起泡排序（比较和移动次数分别为,n-1,和,0,），反之，在待排记录处于,“,逆序,”,时取最大值，此时需进行,n-1,趟起泡 （比较和移动次数分别为,和 ）。,10.3.2,快速排序,快速排序则是通过一趟排序选定一个关键字,介于,“,中间,”,的记录，从而使剩余记录可以分成两,个子序列分别继续排序，通常称该记录为,“,枢轴,”,。,关键字序列,( 52, 49, 80, 36, 14, 75, 58, 97, 23, 61 ),经第,1,趟快速排序之后为,( 23, 49, 14, 36) 52 (75, 58, 97, 80, 61 ),经第,2,趟快速排序之后为,( 14) 23 (49, 36) 52 (61, 58) 75 (80, 97 ),经第,3,趟快速排序之后为,( 14, 23, 36, 49, 52, 58, 61, 75, 80, 97 ),算法,10.9,void,QSort,(,RcdType,R,int,s,int,t ),/,对记录序列,Rs.t,进行快速排序,if,(s t),/,长度大于,1,pivotloc,=,Partition(R, s, t);,/,对,Rs.t,进行一趟快排，并返回枢轴位置,QSort(R, s, pivotloc-1); /,对低子序列递归进行排序,QSort(R, pivotloc+1, t); /,对高子序列递归进行排序,/ if,/,Qsort,算法,10.10,void,QuickSort,(,SqList,&,L),/,对顺序表,L,进行快速排序,QSort(L.r, 1,L.length,);,/,QuickSort,一次划分（一趟快速排序）的算法如下：,算法,演示,int,Partition (,RcdType,R,int,low,int,high),/,对记录子序列,Rlow.high,进行一趟快速排序，并返回枢轴记录,/,所在位置，使得在它之前的记录的关键字均不大于它的关键字，,/,而在它之后的记录的关键字均不小于它的关键字,R0 =,Rlow,;,/,将枢轴记录移至数组的闲置分量,pivotkey,=,Rlow.key,;,/,枢轴记录关键字,while,(lowhigh),/,从表的两端交替地向中间扫描,while,(low=,pivotkey,),-high;,Rlow,+ =,Rhigh,;,/,将比枢轴记录小的记录移到低端,while,(lowhigh,&,Rlow.key,=,pivotkey,),+low;,Rhigh,- =,Rlow,;,/,将比枢轴记录大的记录移到高端,/ while,Rlow, = R0;,/,枢轴记录移到正确位置,return low;,/,返回枢轴位置,/ Partition,可以推证，快速排序的平均时间复杂度为,O,(,nlogn,),，在三者取中的前,提下，对随机的关键字序列，快速排序是目前被认为是最好,的排序方法。,10.4,选择排序法,10.4.1,简单选择排序,选择排序的基本思想是，在待排区段的记录序列中选出关键字最大或最小的记录，并将它移动到法定位置。第,i(i,=1,2,n-1),趟的简单选择排序（序列中前,i-1,个记录的关键字均小于后,n-i+1,个记录的关键字）的作法是，在后,n-i+1,个记录中选出关键字最小的记录，并将它和第,i,个记录进行互换。,算法,10.12,void,SelectSort,(,SqList,&,L),/,对顺序表,L,作简单选择排序,for,(i=1; i,L.length,; +i),/,选择第,i,小的记录，并交换到位,j = i;,for,( k=i+1; k=,L.length,; k+ ),/,在,L.ri.L.length,中选择关键字最小的记录,if,(,L.rk.key,L.rj.key,) j =k ;,if,( i!=j ),L.rj, ,L.ri,;,/,与第,i,个记录互换,/ for,/,SelectSort,10.4.2,树形选择排序,10.4.3,堆排序,若含,n,个元素的序列,k,1, k,2,k,n,满足下列关系则称作,“,小顶堆,”,或,“,大顶堆,”,。,“,堆顶,”,元素为序列中的,“,最小值,”,或,“,最大值,”,。,如：,12, 39, 20, 65, 47, 34, 98, 81, 73, 56,为“小顶堆”；,98, 81, 34, 73, 56, 12, 20, 39, 65, 47,为“大顶堆”。,可将上述数列视为如下的一个完全二叉树 ：,利用堆的特性进行的排序方法即为,“,堆排序,”,，其排序过程如下：假设待排关键字序列为：, 34, 39, 20, 65, 47, 12, 98, 73, 81, 56 ,1,）先将它调整为大顶堆：, 98, 81, 34, 73, 56, 12, 20, 39, 65, 47 ,2,）互换,“,堆顶,”,和待排序列中 的最后的关键字：, 47, 81, 34, 73, 56, 12, 20, 39, 65, 98 ,3,）在待排序列中舍去最大关键字，将其余部分重新调整为堆：, 81, 73, 34, 65, 56, 12, 20, 39, 47 98,4,）重复,2,）和,3,）直至待排序列中只剩一个关键字为止。,堆排序的两个关键问题是：,1,） 如何将一个无序序列调整为堆？,2,）如何在互换堆顶之后重新调整为堆？,演示,演示,算法,10.13,void,HeapAdjust,(,SqList,&,H,int,s,int,m),/,已知,H.rs.m,中记录的关键字除,H.rs.key,之外均满足堆的定义，,/,本函数依据关键字的大小对,H.rs,进行调整，使,H.rs.m,成为一,/,个大顶堆（对其中记录的关键字而言）,H.r0 =,H.rs,;,/,暂存根结点的记录,for,( j=2*s; j=m; j*=2 ),/,沿关键字较大的孩子结点向下筛选,if,( jm,&,H.rj.key,=,H.rj.key,),break,;,/,不需要调整，跳出循环,H.rs, =,H.rj,; s = j;,/,将大关键字记录往上调,/ for,H.rs, = H.r0;,/,回移筛选下来的记录,/,HeapAdjust,算法,10.14,演示,void,HeapSort,(,SqList,&,H ),/,对顺序表,H,进行堆排序,for,( i=H.length/2; i0; -i ),/,将,H.r1.H.length,建成大顶堆,HeapAdjust,( H, i,H.length,);,H.r1 ,H.rH.length,; /,互换,堆顶,和,堆底,的记录,for,( i=H.length-1; i1; -i ),HeapAdjust(H, 1, i);,/,从根开始调整，将,H.r1.i,重新调整为大顶堆,H.r1 ,H.ri,;,/,互换,“,堆顶,”,和当前的,“,堆底,”,，使已有序的记录沉积在底部,/for,/,HeapSort,可以证明，堆排序的时间复杂度为,O,(,nlogn,),。和选择排序同，无,论待排序列中的记录是正序还是逆序排列，都不会使堆排序,处于,最好,或,最坏,的状态。,10.5,归并排序法,10.5.1 2-,路归并排序,归并排序的基本操作是将两个或两个以上的记录有序序列归并为一个有序序列。,2-,路归并排序则是归并排序中的一种最简单的情况，它的基本操作是将两个相邻的有序子序列,“,归并,”,为一个有序序列。,算法,10.15,void,Merge (,RcdType,SR,RcdType,TR,int,i,int,m,int,n),/,将有序的,SRi.m,和,SRm+1.n,归并为有序的,TRi.n,for,(j=m+1, k=i; i=m,&,j=n; +k),/,将,SR,中记录按关键字从小到大地复制到,TR,中,if,(,SRi.key,=,SRj.key,),TRk, =,SRi,+;,else,TRk, =,SRj,+;,while,(i=m),TRk,+ =,SRi,+;,/,将剩余的,SRi.m,复制到,TR,while,(j=n),TRk,+ =,SRj,+;,/,将剩余的,SRj.n,复制到,TR,/ Merge,算法,10.16,演示,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);,/,递归地将,SRs.m,归并为有序的,TR2s.m,Msort,(SR,TR2,m+1, t);,/,递归地将,SRm+1.t,归并为有序的,TR2m+1.t,Merge (TR2,TR1,s,m,t);,/,将,TR2s.m,和,TR2m+1.t,归并到,TR1s.t,/ else,/,Msort,算法,10.17,void,MergeSort,(,SqList,&,L),/,对顺序表,L,作,2-,路归并排序,MSort(L.r,L.r, 1,L.length,);,/,MergeSort,10.6,基数排序,10.6.1,多关键字的排序,通常实现多关键字排序可以有两种策略：,一是最,主位优先,（,MSD,法）,另一是,最次位优先,（,LSD,法）。,演示,假设记录的逻辑关键字由,d,个,“,关键字,”,构成，每个关键字可能取,rd,个值，则只要从,最低位关键字,起，按关键字的不同值将记录,“,分配,”,到,rd,个队列之后再,“,收集,”,在一起，如此重复,d,趟，最终完成整个记录序列的排序。按这种方法实现的排序称为,“,基数排序,”,，其中,“,基数,”,即,rd,指的是,“,关键字,”,的取值范围。,演示,10.6.2,链式基数排序,演示,附设指针数组将顺序表视作一个,静态链表,，利用,修改指针,实现分配和收集。同时设置,rd,个队列的头指针和尾指针，分别指示各队列的,头结点,和,尾结点,在链表中的位置。,算法,10.19,void,Distribute (,RcdType,R,int,k,int,f,int,e),/ R,中记录已按,(R.keysk+1,.,R.keysL.bitsnum-1),有序，,/,本算法按,R.keysk,建立,RADIX,个子表，使同一子表中记录的,/,keysk,相同。,f0.RADIX-1,和,e0.RADIX-1,分别指向各子,/,表中第一个和最后一个记录,for,(j=0; jRadix; +j),fj, = 0;,/,各子表初始化为空表,for,(p=Next0; p; p=,Nextp,),j =,ord(Rp.keysk,);,/,ord,将记录中的关键字,keysk,映射到,0.RADIX-1,中,if,(,!,fj, ),fj, = p;,else,Nextej, = p;,ej, = p;,/,将,p,所指的结点插入相应子表,/ for,/ Distribute,算法,10.20,void,Collect (,RcdType,R,int,k,int,f,int,e),/,本算法按,R.keysk,自小至大地将,f0.RADIX-1,所指各子表,/,依次链接成一个链表，,e0.RADIX-1,为各子表的尾指针,for,( j=0;,!,fj,; j=,succ(j,);,/,找第一个非空子表，,succ,为求后继函数,Next0 =,fj,; t =,ej,;,/ Next0,指向第一个非空子表中第一个结点,while,( jRADIX ),for,(j=,succ(j,); jRADIX-1,&,!,fj,; j=,succ(j,) );,/,找下一个非空子表,if,(,fj, ),rt.next,=,fj,; t =,ej,;,/,链接两个非空子表,/ while,Nextt, = 0;,/ t,指向最后一个非空子表中的最后一个结点,/ Collect,链式基数排序的时间复杂度为,O,(,d(n+rd,),，或简写为,O,(,dn,),。,10.7,各种排序方法的综合比较,一、 时间性能,1.,按平均的时间性能来分，有三类排序方法：时间复杂度为,O,(,nlogn,),的方法有：快速排序、堆排序和归并排序，其中快速排序目前被认为是最快的一种排序方法，后两者之比较，在,n,值较大的情况下，归并排序较堆排序更快；时间复杂度为,O,(n,2,),的有：插入排序、起泡排序和选择排序，其中以插入排序为最常用，特别是对于已按关键字基本有序排列的记录序列尤为如此，选择排序过程中记录移动次数最少；时间复杂度为,O,(n),的排序方法只有基数排序一种。,2.,当待排记录序列按关键字顺序有序时，插入,排序和起泡排序能达到,O,(n),的时间复杂度；而对,于快速排序而言，这是最不好的情况，此时的时,间性能蜕化为,O,(n,2,),，因此应尽量避免。,3.,选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。,4.,以上对排序的时间复杂度的讨论主要考虑排序过程中所需进行的关键字间的比较次数，当待排序记录中其它各数据项比关键字占有更大的数据量时，还应考虑到排序过程中移动记录的操作时间，有时这种操作的时间在整个排序过程中占的比例更大，从这个观点考虑，简单排序的三种排序方法中起泡排序效率最低。,二、空间性能,指的是排序过程中所需的辅助空间大小。,1.,所有的简单排序方法（包括：插入、起泡和选择排序）和堆排序的空间复杂度均为,O,(1),。,2.,快速排序为,O,(,logn,),，为递归程序执行过程中栈所需的辅助空间。,3.,归并排序和基数排序所需辅助空间最多，其空间复杂度为,O,(n),。,三、排序方法的稳定性能,1.,除希尔排序、快速排序和堆排序是不稳定的排序方法外，本章讨论的其它排序方法都是稳定的。例如：对关键字序列,(4,1,3,4,2,2),进行快速排序，其结果为,(2,3,4,2,4,1,),。,2. ,稳定性,是由方法本身决定的。一般来说，排序过程中所进行的比较操作和交换数据仅发生在相邻的记录之间，没有大步距的数据调整时，则排序方法是稳定的。而对不稳定的排序方法，不论其算法的描述形式如何，总能举出一个说明它不稳定的实例来。,【,本章小结,】,本章主要讨论各种内部排序的方法。学习本章的目的是了解各种排序,方法的原理以及各自的优缺点，以便在编制软件时能按照情况所需合理选用。一般来说，在选择排序方法时，可有下列几种选择：,1),若待排序的记录个数,n,值较小（例如,n30,），则可选用插入排序法，但若记录所含数据项较多，所占存储量大时，应选用选择排序法。反之，若待排序的记录个数,n,值较大时，应选用快速排序法。但若待排序记录关键字有,有序,倾向时，就慎用快速排序，而宁可选用堆排序或归并排序，而后两者的最大差别是所需辅助空间不等。,2),快速排序和归并排序在,n,值较小时的性能不及直接插入排序，因此在实际应用时，可将它们和插入排序,混合,使用。如在快速排序划分子区间的长度小于某值时，转而调用直接插入排序；或者对待排记录序列先逐段进行直接插入排序，然后再利用,归并操作,进行两两归并直至整个序列有序为止。,3),基数排序的时间复杂度为,O,(,dn,),，因此特别适合于待排记录数,n,值很大，而关键字,位数,d ,较小的情况。并且还可以调整,基数,（如将基数定为,100,或,1000,等）以减少基数排序的趟数,d,的值。,4),一般情况下，对单关键字进行排序时，所用的排序方法是否稳定无关紧要。但当按,最次位优先,进行多关键字排序时,(,除第一趟外,),必须选用稳定的排序方法。,