算法课件--第9章(内排序)

,North China Electric Power University,第九章 内排序,基本概念,插入排序,冒泡排序,选择排序,计数排序,希尔排序,堆排序,快速排序,合并排序,基数排序,设含有,n,个记录的文件,R,1,R,2,，,R,n,其相应的关键字为,K,1,K,2,，,K,n,，,需确定一种排列,P(1),P(2),P(n),使其相应的关键字满足如下的递增,(,或递减,),关系：,K,P(1),K,P(2),K,P(3),K,P(n),即，使上述文件成为一个按其关键字线性有序的文件,R,P(1),R,P(2),，,R,P(n),这样一种运算称为排序。,9.1,基本概念,如果在排序期间具有相同关键字的记录的相对位置不变，则称此方法是,稳定的,。,排序：,排序的稳定性：,即，,1),K,(i),K,(i+1),(1,i n-1),2),若在输入文件中,ij,且,K,i,=K,j,则在经过排序后,的文件中仍,R,i,先于,R,j,排序,内排序：整个排序过程都在内存进行的排序。,外排序：当文件很大以至于内存不足以存放全部记录，在排序过程中需要对外存进行存取访问。,例如：,将下列关键字序列,52,49,80,36,14,58,61,23,97,75,调整为,14,23,36,49,52,58,61,75,80,97,内部排序的方法,在排序的过程中，参与排序的记录序列中存在两个区域：有序区和无序区。,内部排序的过程是一个逐步扩大记录的有序序列长度的过程。,使有序区中记录的数目增加一个或几个的操作称为,一趟,排序。,存放待排序数据的数据结构：,typedef,struct,int,key;,datatype,otheritem,;/,其他域,records;,typedef,struct,records Listn+1;,逐步扩大记录有序序列长度的方法大致有下列几类：,1.,插入类,:,将无序子序列中的一个或几个记录“插入”到有序序列中，从而增加记录的有序子序列的长度；,2.,交换类,:,通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度；,3.,选择类,:,从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度；,4.,归并类,:,通过“归并”两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度；,5.,其它方法。,内,排 序,插入类排序,直接插入排序,折半插入排序,希尔排序,交换类排序,冒泡排序,快速排序,选择类排序,选择排序,堆排序,归并类排序,归并排序,其他排序,计数排序,基数排序,9.2,计数排序,对每个记录计算文件中有多少个其它记录的关键字大于该记录的关键字值，从而找到该记录的正确排序位置。,key info count,设一个记录有三个域：,关键字域,该记录的其他信息域,计数域,排序算法的思想：,for(i=1;in;i+),for(j=i+1;j=n;j+),if(Ri.key)Rj.key),Ri.count=Ri.count+1;,else,Rj.count=Rj.count+1;,void,countsort(List,R,int,n),for(i=1;i=n;i+),Ri.count=1;/,对所有元素的,count,域置,1,；,算法如下：,设文件有,n,个记录，则外循环：,i=1,时，内循环要做,n-1,次比较；,i=2,时，内循环要做,n-2,次比较；,i=n-1,时，内循环要做,1,次比较；,总的比较次数为,(n-1)+(n-2)+1=n(n-1)/2,算法性能分析：,所以，算法所需时间为,O(n,2,),，,由于不需要记录移动和额外空间，同时算法简单，当,n,较小时，可采用本算法。,例 关键字序列,46,，,55,，,13,，,42,，,44,，,17,，,05,，,70,关键字,46,55,13,42,44,17,05,70,初始化,1,1,1,1,1,1,1,1,i=1,3,1,2,2,2,2,2,1,i=2,3,2,3,3,3,3,3,1,i=3,3,2,7,3,3,3,4,1,i=4,3,2,7,5,3,4,5,1,i=5,3,2,7,5,4,5,6,1,i=6,3,2,7,5,4,6,7,1,i=7,3,2,7,5,4,6,8,1,9.3,直接插入排序,假设在排序过程中，记录序列,R1.n,的状态为：,则一趟插入排序的基本思想为：将记录,Ri,插入到有序子序列,R1.i-1,中，使记录的有序序列从,R1.i-1,变为,R1.i,。,显然，完成这个“插入”需分三步进行：,1,查找,Ri,的插入位置,j+1,；,2,将,Rj+1.i-1,中的记录后移一个位置；,3,将,Ri,复制到,Rj+1,的位置上。,直接插入排序,：,利用顺序查找实现“在,R1.i-1,中查找,Ri,的插入位置”的插入排序。,注意直接插入排序算法的三个要点：,1.,从,Ri-1,起向前进行顺序查找，监视哨设置在,R0,；,R0=Ri,；,设置“哨兵”,j=i-1;,while(R0.keyRj.key),j=j-1;/,从后往前找,Return(j+1);,返回,Ri,的插入位置为,j+1,2.,对于在查找过程中找到的那些关键字不小于,Ri.key,的记,录，并在查找的同时实现记录向后移动；,while(R0.keyRj.key),Rj+1=Rj;j=j-1;,3.i=2,，,3,，,n,实现整个序列的排序。,排序算法如下：,void,insort(List,r,int,n),/,r,为给定的表，其记录为,ri,，,i=0,，,1,，,，,n,，,x,为暂存单元。,for(i=2;i=n;i+),r0=ri;/,r0,作为标志位,j=i-1;,while(r0.keyrj.key),rj+1=rj;,j-;,/,j,从,i-1,至,0,，,rj.key,与,ri.key,进行比较,rj+1=r0;,/,insort,排序的时间分析：,实现排序的基本操作有两个：,（,1,）“比较”序列中两个关键字的大小；,（,2,）“移动”记录。,对于直接插入排序：,最好的情况（关键字在记录序列中顺序有序）：,最坏的情况（关键字在记录序列中逆序有序）：,“比较”的次数：,“移动”的次数：,总的说来，直接插入排序所需进行关键字间的比较次数和记录移动的次数均为,n,2,/4,，,所以直接插入排序的时间复杂度为,O(n,2,),。,“比较”的次数：,“移动”的次数：,2(n-1),9.4,折半插入排序,排序算法的思想：,由于直接插入排序的内循环,(,从,1,到,i-1),的查找,(,或说是比较,),是在,(,部分,),有序表的环境下进行的，所以内循环用“折半查找法”，比用顺序查找法快。,算法描述如下：,void,binsort(List,r,int,n),for(i=2;i=n;i+),r0=ri;low=1;high=i-1;,while(low=high),m=(low+high)/2;,if r0.keyrm.key,high=m-1;,else,low=m+1;,for(j=i-1;j=low;j-),rj+1=rj;/,把从第,low,起到第,i-1,各记录后移,rlow=r0;/,将第,i,个记录插入,/,binsort,9.5,冒泡排序,排序算法的思想：,比较,k,1,和,k,2,如果这些关键字的值不符合排序顺序,就交换,k,1,和,k,2,；,然后对记录,k,2,和,k,3,k,3,和,k,4,等等进行相同的工作。直到,k,n-1,和,k,n,为止,到此得到一个最大,(,或最小,),关键字值存在,k,n,的位置上,(,通常将,此过程叫做一趟,),。重复这个过程,就得到在位置,k,n-1,k,n-2,等处的适当记录,使得所有记录最终被排好序。,例如,:,将,5,个记录的关键字,7,4,8,3,9,进行冒泡排序。排序后,k1k2,kn,(n=5),。,7 4 4 3 3,4 7 3 4 4,8 3 7 7 7,3 8 8 8 8,9 9 9 9 9,因为到第四趟就没有交换的偶对了,所以整个排序结束。,算法描述如下,:,void,bubblesort(List,r,int,n),for(m=1;m=n;m+),scanf(“%d”,rm,);,k=n;,do,all=T;,/all=T,标志没有交换的,;all=F,标志有交换的,for(m=1;mri),max=rm;rm=ri;,ri,=max;all=F;,k-;,while(all=,F)&(k,!=1),冒泡排序的结束条件为：最后一趟没有进行“交换”。冒泡排序是一种,稳定的,排序算法。,时间分析,:,最好的情况（关键字在记录序列中顺序有序）：只需进行一趟起泡,“比较”的次数：,“移动”的次数：,n-1,0,最坏的情况（关键字在记录序列中逆序有序）：需进行,n-1,趟起泡,“比较”的次数：,“移动”的次数：,9.6,希尔排序,基本思想：,对待排序记录序列先作“宏观”调整，再作“微观”调整。所谓“宏观”调整，指的是，“跳跃式”的插入排序。即：将记录序列分成若干子序列，每个子序列分别进行插入排序,待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。,假设将,n,个记录分成,d,个子序列，则这,d,个子序列分别为：,R1,，,R1+d,，,R1+2d,，,，,R1+kd,R2,，,R2+d,，,R2+2d,，,，,R2+kd,Rd,，,R2d,，,R3d,，,，,Rkd,，,R(k+1)d,其中，,d,称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为,1,。,例如：,第二趟希尔排序，设增量,d=3,第三趟希尔排序，设增量,d=1,希尔排序的算法描述如下,:,void,ShellInsert,(List,r,int,d),/,本算法对直接插入算法作了以下修改：,/1.,前后记录位置的增量是,d,，,而不是,1,；,/2.r0,只是暂存单元，不是哨兵。当,j=0,时，插入位置已找到。,for(i=d+1;i=n;i+),if(ri 0)and(r0 rj),rj+d=rj;/,记录后移，查找插入位置,j=j-d;,rj+d=r0;/,插入,for(i=2;i=n;i+),r0=ri;,j=i-1;,while(r0.keyrj.key),rj+1=rj;,j=j-1;,rj+1=r0;,Void Shell_sort(List r,int,dlta,int,t);,/,按增量序列,dlta0.t-1,对顺序表,r,作希尔排序,for(k=0;k=,t;k,+),ShellInsert(r,dltak,);,先取定一个两项之间的距离,d,1,(n,其中,n,为整个表的长度,),反复比较每两个相距,d,1,的项,直到以,d,1,为距离划分的组排序好为止,(,至此一趟排序完成,);,然后取,d,2,d,1,再继续以,d,2,为距离反复比较每两个相距为,d,2,的项,依此类推,.,取每个,d,i+1,d,i,直到,d,t,=1,为止。,例如,假设文件中,8,个记录的关键字,我们不采用顺序比较,而是先从第一个关键字开始每隔,4,个关键字进行比较,;,同理第二个也从隔,4,个关键字进行比较,第三个,第四个,依次做下去,.,题中选,d1=4,从小到大排序,:,例,初始,d1=4,46 55 13 42 94 17 05 70,55与17,13与05,第一趟后结果,46 17 05 42 94 55 13 70,46与05,94与13,46与13,第二趟后结果,d2=2,05 17 13 42 46 55 94 70,13,46,分,别交换两,次,05 13 17 42 46 55 70 94,第三趟后结果,d3=1,13与17,94与70,North China Electric Power Universit