九章排序.ppt

单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,第九章 排序,概述,插入排序,交换排序,选择排序,归并排序,*基数排序,*外排序,排序,：,将一组杂乱无章的数据按一定的规律顺次排列起来。,数据表(,datalist,),:,它是待排序数据对象的有限集合。,排序码(,key,),:,通常数据对象有多个属性域,即多个数据成员组成,其中有一个属性域可用来区分对象,作为排序依据。该域即为,排序码,。每个数据表用哪个属性域作为排序码，要视具体的应用需要而定。,9.1,概述,排序算法的稳定性,:,如果在对象序列中有两 个对象,r,i,和,r,j,它们的排序码,k,i,=k,j,且在排序之前,对象,r,i,排在,r,j,前面。如果在排序之后,对象,r,i,仍在对象,r,j,的前面,则称这个排序方法是稳定的,否则称这个排序方法是不稳定的。,内排序与外排序,:,内排序是指在排序期间数据对象全部存放在内存的排序；外排序是指在排序期间全部对象个数太多，不能同时存放在内存，必须根据排序过程的要求，不断在内、外存之间移动的排序。,排序的时间开销,:,排序的时间开销是衡量算法好坏的最重要的标志。排序的时间开销可用算法执行中的,数据比较次数,与,数据移动次数,来衡量。,算法执行时所需的附加存储,:,评价算法好坏的另一标准。,算法运行时间代价的大略估算一般都,按平均情况,进行估算。受对象排序码序列初始排列及对象个数影响较大的，需要按,最好情况,和,最坏情况,进行估算。,基本思想,:当插入第,i,(,i,1),个对象时,前面的,V0,V1,V,i,-,1,已经排好序。这时,用,V,i,的排序码依次与,V,i,-,1,V,i,-,2,的排序码顺序进行比较,找到插入位置即将,V,i,插入,原来位置上的对象向后顺移。,基本方法,:每步将一个待排序的对象,按其排序码大小,插入到前面已经排好序的一组对象的适当位置上,直到对象全部插入为止。,1.直接插入排序,(,Insert Sort),9.2,插入排序(,Insert Sorting),16,49,16,16,21,25,49,25*,16,08,0 1 2 3 4 5,0 1 2 3 4 5,temp,21,25,49,25*,08,i,=4,时的排序过程,0 1 2 3 4 5,temp,21,25,49,25*,完成,16,08,16,i,=4,j,=3,i,=4,j,=2,25,25*,16,16,21,25,49,25*,08,0 1 2 3 4 5,0 1 2 3 4 5,temp,21,49,25*,08,0 1 2 3 4 5,temp,21,25,49,25*,16,08,16,16,25,21,i,=4,j,=1,i,=4,j,=0,i,=4,j,=,-,1,16,直接插入排序的算法,template,void,dataList,:,InsertSort(),/,按排序码,Key,非递减顺序对表进行排序,Element,temp,;int,i,j,;,for,(i=1,;,i CurrentSize,;,i+),if,(Vectori 0,;,j,-,),/,从后向前顺序比较,if,(temp Vectorj,-,1),Vectorj=Vectorj,-,1,;,else break;,算法分析,排序码比较次数和对象移动次数与对象排序码的初始排列有关。,最好情况,下,排序前对象已按排序码从小到大有序,每一个对象比较1次,移动2次对象,总的排序码比较次数为,n,-,1,对象移动次数为,2(,n,-,1),。,Vectorj=temp,;,最坏情况,下,总排序码比较次数,KCN,和对象移动次数,RMN,分别为,平均情况下排序的时间复杂度为,O(,n,2,),。,直接插入排序是一种,稳定,的排序方法。,2.,折半插入排序(,Binary Insertsort),基本思想是:设在顺序表中有一 个对象序列,V0,V1,V,n,-,1,。,其中,V0,V1,V,i,-,1,是已经排好序的对象。在插入,V,i,时,利用折半搜索法寻找,V,i,的插入位置。,折半插入排序的算法,template,void,dataList:,BineryInsSort(),Element,temp,;,int,Left,Right,;,for,(,int,i=1,;,i CurrentSize,;,i+),Left=0,;,Right=i,-,1,;,temp=Vectori,;,while,(Left=Right),int,middle=(Left+Right)/2,;,if,(temp=Left,;,k,-,),Vectork+1=Vectork,;,VectorLeft=temp,;,折半搜索比顺序搜索查找快,所以折半插入排序就,平均性能,来说比直接插入排序要快。,它所需的排序码比较次数与待排序对象序列的初始排列无关,仅依赖于对象个数,。在插入第,i,个对象时,需要经过,log,2,i,+1,次排序码比较,才能确定它应插入的位置。因此,将,n,个对象(为推导方便,设为,n,=2,k,),用折半插入排序所进行的排序码比较次数为：,折半插入排序是一个稳定的排序方法。,算法分析,排序码比较次数:,当,n,较大时,总排序码比较次数比直接插入排序的最坏情况要好得多,但比其最好情况要差。,对象移动次数:,折半插入排序的对象移动次数与直接插入排序相同,依赖于对象的初始排列。,4.希尔排序(,Shell Sort),希尔排序方法又称为,缩小增量排序,。,基本思想,:,设待排序对象序列有,n,个对象,首先取一个整数,gap n,作为间隔,将下标相差为,gap,的倍数对象放在一组。,在组内作插入排序。,然后缩小间隔,gap,例如取,gap=,gap/2,，,重复上述的组划分和排序工作。直到最后取,gap,=,1,将所有对象放在同一个组中进行排序为止。,例：,99,14,28,31,2,7,46,70,62,180,30,82,170,5,9,21,25,49,25*,16,08,0 1 2 3 4 5,21,25*,i,=1,08,49,Gap=3,25,16,49,25,16,08,49,25*,08,21,25,21,25*,16,21,25,49,25*,16,08,0 1 2 3 4 5,21,i,=2,08,49,Gap=2,25,16,49,16,25*,08,21,25,49,25*,08,16,21,25*,25,21,25,49,25*,16,08,0 1 2 3 4 5,21,i,=3,08,Gap=1,25,16,49,25*,开始时,gap,的值较大,子序列中的对象较少,排序速度较快;随着排序进展,gap,值逐渐变小,子序列中对象个数逐渐变多,由于前面工作的基础,大多数对象已基本有序,所以排序速度仍然很快。,希尔排序的算法,template,void,dataList,:,ShellSort(),Element,temp,;,int,gap=CurrentSize/2,;,/,gap,是子序列间隔,while,(gap!=0),/,循环,直到,gap,为零,for,(,int,i=gap,;,i=gap,;,j,-,=gap),if,(temp Vectorj,-,gap),Vectorj=Vectorj,-,gap,;,else break;,Vectorj=temp,;,gap=(,int,)(gap/2,),;,Gap,的取法有多种。最初,shell,提出取,gap=,n/2,，,gap=,gap/2,，,直到,gap=1,。Knuth,提出取,gap=,gap/3,+1,。,还有人提出都取奇数为好，也有人提出各,gap,互质为好。,对特定的待排序对象序列，可以准确地估算排序码的比较次数和对象移动次数,。,想要弄清排序码比较次数和对象移动次数与增量（,gap）,选择之间的依赖关系，并给出完整的数学分析，还没有人能够做到。,Knuth,利用大量实验统计资料得出:当,n,很大时，排序码平均比较次数和对象平均移动次数大约在,n,1.25,到 1.6,n,1.25,的范围内。这是在利用直接插入排序作为子序列排序方法的情况下得到的。,基本思想,：设待排序对象序列中的对象个数为,n,。,最多作,n,-,1,趟，,i,=1,2,n,-,1,。,在第,i,趟中,从后向前,，,j,=,n,-,1,n,-,2,i,，,顺次两两,比较,V,j,-,1.k,ey,和,V,j,.k,ey,。,如果发生逆序，则交换,V,j,-,1,和,V,j,。,基本方法,：,两两比较待排序对象的排序码,如果发生逆序，则交换之。直到所有对象都排好序为止。,1.起泡排序,(,Bubble Sort),9.3,交换排序(,Exchange Sort),21,25,49,25*,16,08,0 1 2 3 4 5,21,25*,i,=1,49,25,16,25,16,08,49,Exchang,=1,08,25*,49,21,Exchang,=1,i,=2,i,=3,08,16,Exchang,=1,25*,25,21,25*,0 1 2 3 4 5,i,=4,49,16,Exchang,=0,08,25,21,起泡排序的算法,template,void,dataList,:,BubbleSort(),int,pass=1,;,int,exchange=1,;,while,(pass=pass,;,j,-,),if,(Vectorj,-,1 Vectorj),/,逆序,Swap(Vectorj,-,1,Vectorj),;,/,交换,exchange=1,;,/,标志置为,1,有交换,pass+,;,第,i,趟对待排序对象序列,V,i,-,1,V,i,V,n,-,1,进行排序,结果,将该序列中排序码最小的对象交换到序列的第一个位置,(,i,-,1),其它对象也都向排序的最终位置移动。,最多做,n,-,1,趟起泡就能把所有对象排好序。,最好的情形:,在对象的初始排列已经按排序码从小到大排好序时,此算法只执行一趟起泡,做,n,-,1,次排序码比较,不移动对象。,最坏的情形:,算法执行,n,-,1,趟起泡,第,i,趟(1,i,n,),做,n,-,i,次排序码比较,执行,n,-,i,次对象交换。这样在最坏情形下总的排序码比较次数,KCN,和对象移动次数,RMN,为：,起泡排序需要一个额外空间以实现对象值的对换。,起泡排序是一个,稳定,的排序方法。,2.快速排序(,Quick Sort),基本思想:,任取待排序对象序列中的某个对象(例如取第一个对象)作为基准,按照该对象的排序码大小,将整个对象序列划分为左右两个子序列：,左侧子序列中所有对象的排序码都小于或等于基准对象的排序码。右侧子序列中所有对象的排序码都大于基准对象的排序码。,基准对象则排在这两个子序列中间(这也是该对象最终应安放的位置)。,递归地对这两个子序列进行快速排序，直到所有的对象都排在相应位置上为止,。,QuickSort(List),if(,List,的长度大于1,),将序列,List,划分为两个子序列,LeftList,和,Right List;,QuickSort(LeftList);,QuickSort(RightList);,将两个子序列,LeftList,和,RightList,合并为一个序列,List;,算法描述,快速排序的算法思想,分治法,分（难）,合并（容易）,初始关键字：,28 19 27 48 56 12 10 25 20 50,完成第一趟后,20 19 27 25 10 12,28,56 48 50,完成第二趟,12 19 10,20,25 27 28 50 48,56,完成第三趟,10,12,19 20,25,27 28 50 48 56,快速排序的算法,template,void,dataList,:,QuickSort(,const int,left,const int,right),/,在序列,left,right,中递归地进行快速排序,if,(left right),int,pivotpos=Partition(left,right),;,/,划分,/,对左序列同样处理,QuickSort(left,pivotpos,-,1),;,/,对右序列同样处理,QuickSort(pivotpos+1,right),;,int,dataList,:,Partition(,int,s,int,t),int,x,i,j;,x=Vectors;i=s;j=t;,while,(i j),while,(i=x)j=j-1;,if(ij)ai=aj;,while,(i j),if(ij)aj=ai;,Vectori=x;,return,i;,从快速排序算法的递归树可知,快速排序的,趟数,取决于,递归树的高度,。,附加存储开销,:取决于最大递归调用层次数，与递归树的高度一致。,理想情况:,log,2,(,n,+1),。,因此，附加存储开销为,O(log,2,n,),。,最坏的情况:,待排序对象序列已经按其排序码从小到大排好序的情况下,其递归树成为单支树,每次划分只得到一个比上一次少一个对象的子序列。必须经过,n,-1,趟才能把所有对象定位，附加存储开销为,O(,n,),。,算法分析,时间开销,:,理想情况:,O(,n,log,2,n,),最坏的情况:,O(,n,2,),待排序对象把所有对象定位,而且第,i,趟需要经过,n-i,次排序码比较才能找到第,i,个对象的安放位置，总的排序码比较次数将达到,快速排序是一种,不稳定,的排序方法。,对于,n,较大的平均情况而言,快速排序是“快速”的,但是当,n,很小时,这种排序方法往往比其它简单排序方法还要慢。,基本思想,:每一趟(例如第,i,趟,i,=0,1,n,-,2),在后面,n,-,i,个待排序对象中选出排序码最小的对象,作为有序对象序列的第,i,个对象。待到第,n,-,2,趟作完,待排序对象只剩下1个,就不用再选了。,9.4,选择排序,直接选择排序是一种简单的排序方法,它的基本步骤是：,在一组对象,V,i,V,n,-,1,中选择具有最小排序码的对象；,若它不是这组对象中的第一个对象,则将它与这组对象中的第一个对象对调;,在这组对象中剔除这个具有最小排序码的对象。在剩下的对象,V,i,+1V,n,-,1,中重复执行第,、,步,直到剩余对象只有一个为止。,1.直接选择排序,(,Select Sort),21,25,49,25*,16,08,0 1 2 3 4 5,21,25*,i,=0,49,25,16,25,16,08,49,08,25*,49,21,i,=1,i,=2,08,16,25*,25,21,初始,最小者,08,交换,21,08,最小者,16,交换25,16,最小者,21,交换49,21,49,25*,0 1 2 3 4 5,25*,i,=4,25,16,08,49,25*,49,21,结果,i,=3,08,16,25,21,最小者,25*,无交换,最小者,25,无交换,25,21,16,08,各趟排序后的结果,直接选择排序的算法,template,void,dataList,:,SelectSort(),for,(,int i,=0,;i,CurrentSize,-,1,;,i,+,),int,k=i,;,/,当前定位的对象,for,(,int,j=i+1,;,j CurrentSize,;,j+),if,(Vectorj,Vectork),k=j,;,/,当前具最小排序码的对象,if,(k!=i),/,对换到第,i,个位置,Swap(Vectori,Vectork,),;,利用堆及其运算,可以很容易地实现选择排序的思路。,堆排序分为两个步骤：,根据初始输入数据，利用堆的调整算法,FilterDown(),形成初始堆;,通过一系列的对象交换和重新调整堆进行排序。,3.堆排序,(,Heap Sort),建立初始的最大堆,21,25,25*,49,16,08,0,1,2,3,4,5,i,21,25,25*,16,49,08,0,2,5,4,3,1,i,21 25 49 25*16 08,初始排序码集合,21 25 49 25*16 08,i,=2,时的局部调整,21,25,25*,49,16,08,0,1,2,3,4,5,i,49,25,25*,16,21,08,0,2,5,4,3,1,21 25 49 25*16 08,49 25 21 25*16 08,i,=0,时的局部调整,形成最大堆,i,=1,时的局部调整,最大堆的向下调整算法,template void,MaxHeap,:,FilterDown(,const int,i,const int,EndOfHeap),int,current=i,;,int,child=2*i+1,;,Type,temp=heapi,;,while,(child=EndOfHeap),/,最后位置,if,(child+1 EndOfHeap,&,heapchild=heapchild),break;,/,temp,排序码大,不做调整,else,heapcurrent=heapchild,;,/,大,子女上移,current=child,;,/,向下继续调整,child=2*child+1,;,heapcurrent=temp,;,/,回放到合适位置,将表转换成堆,for,(,int,i=(CurrentSize,-,2)/2,;,i=0,;,i,-,),FilterDown(i,CurrentSize,-,1),;,基于初始堆进行堆排序,最大堆堆顶,V0,具有最大的排序码,将,V0,与,V,n,-,1,对调,把具有最大排序码的对象交换到最后,再对前面的,n,-,1,个对象,使用堆的调整算法,FilterDown(0,n,-,2),重新建立最大堆,具有次最大排序码的对象又上浮到,V0,位置。,再,对调,V0,和,V,n,-,2,调用,FilterDown(0,n,-,3),对前,n,-,2,个对象重新调整，。,如此反复执行，最后得到全部排序好的对象序列。,49,25,25*,21,16,08,0,1,2,3,4,5,08,25,25*,16,21,49,0,2,5,4,3,1,49 25 21 25*16 08,08 25 21 25*16,49,交换 0 号与 5 号对象,5 号对象就位,初始最大堆,25,25*,08,21,16,49,0,1,2,3,4,5,16,25*,08,25,21,49,0,2,5,4,3,1,25 25*21 08 16,49,16 25*21 08,25,49,交换 0 号与 4 号对象,4 号对象就位,从 0 号到 4 号 重新,调整为最大堆,25*,16,08,21,25,49,0,1,2,3,4,5,08,16,25*,25,21,49,0,2,5,4,3,1,25*16 21 08,25,49,08 16 21,25*,25,49,交换 0 号与 3 号对象,3 号对象就位,从 0 号到 3 号 重新,调整为最大堆,21,16,25*,08,25,49,0,1,2,3,4,5,08,16,25*,25,21,49,0,2,5,4,3,1,21 16 08,25*,25,49,08 16,21,25*,25,49,交换 0 号与 2 号对象,2 号对象就位,从 0 号到 2 号 重新,调整为最大堆,16,08,25*,21,25,49,0,1,2,3,4,5,08,16,25*,25,21,49,0,2,5,4,3,1,16 08 21,25*,25,49,08,16,21,25*,25,49,交换 0 号与 1 号对象,1 号对象就位,从 0 号到 1 号 重新,调整为最大堆,堆排序的算法,template void,MaxHeap,:,HeapSort(),/,对表,heap0,到,heapn,-,1,进行排序,使得表中,/,各,个对象按其排序码非递减有序,。,for,(,int,i=(CurrentSize,-,2)/2,;,i=0,;,i,-,),FilterDown(i,CurrentSize,-,1),;,/,初始堆,for,(i=CurrentSize,-,1,;,i=1,;,i,-,),Swap(heap0,heapi),;,/,交换,FilterDown(0,i,-,1),;,/,重建最大堆,堆排序的,时间复杂性,为,O(,n,log,2,n,)。,附加存储,主要是在第二个,for,循环中用来执行对象交换时所用的一个临时对象。因此，该算法的空间复杂性为,O(1)。,堆排序是一个,不稳定,的排序方法,。,算法分析,归并:是将两个或两个以上的有序表合并成一个新的有序表。,对象序列,initList,中两个有序表,V,l,V,m,和,V,m,+1 V,n,。,它们可归并成一个有序表,存于另一对象序列,mergedList,的,V,l,V,n,中。,这种归并方法称为,两路归并,(2-,way merging)。,设变量,i,和,j,分别是表,V,l,V,m,和,V,m,+1 V,n,的当前检测指针。变量,k,是存放指针。,9.4,归并排序(,Merge Sort),08 21 25 25*49 62 72 93,16 37 54,left mid mid+1 right,initList,i j,08 16 21 25 25*37 49 54 62 72 93,left right,k,mergeList,当,i,和,j,都在两个表的表长内变化时,根据对应项的排序码的大小,依次把排序码小的对象排放到新表,k,所指位置,中；,当,i,与,j,中有一个已经超出表长时，将另一 个表中的剩余部分照抄到新表中。,1.迭代的归并排序算法,基本思想:,假设初始对象序列有,n,个对象，首先把它看成是,n,个长度为 1 的有序子序列(归并项)，先做两两归并，得到,n,/2,个长度为 2 的归并项(如果,n,为奇数，则最后一个有序子序列的长度为1)；再做两两归并，如此重复，最后得到一个长度为,n,的有序序列。,两路归并算法,template void,dataList,:,merge(dataList,&,mergedList,const,int,left,const int,mid,const int,right),int,i=left,j=mid+1,k=left,;,while,(i=mid,&,j=right),/,两两比较,if,(Vectori=Vectorj),mergedList.Vectork=Vectori,;,i+,;,k+,;,else,mergedList.Vectork=Vectorj,;,j+,;,k+,;,if,(i=mid),for,(,int,n1=k,n2=i,;,n2=mid,;,n1+,n2+),mergedList.Vectorn1=Vectorn2,;,else,for,(,int,n1=k,n2=j,;,n2=right,;,n1+,n2+),mergedList.Vectorn1=Vectorn2,;,一趟归并排序的情形,设,initList.Vector0,到,initList.Vector,n-,1,中,n,个对象,已经分为一些长度为,len,的归并项,将这些归并项两两归并,归并成长度为,2,len,的归并项,结果放到,mergedList.Vector,中。,如果,n,不是,2,len,的整数倍,则一趟归并到最后,可能遇到两种情形：,剩下一个长度为,len,的归并项和另一个长度不足,len,的归并项,可用,merge,算法,将它们归并成一个长度小于,2,len,的归并项。,只剩下一个归并项，其长度小于或等于,len,将它直接抄到,MergedList.Vector,中。,template void,datalist,:,MergePass(dataList,&,mergedList,const int,len),int,i=0,;,while,(i+2*len=CurrentSize,-,1),merge(mergedList,i,i+len,-,1,i+2*len,-,1),;,i+=2*len,;/,循环两两归并,if,(i+len=CurrentSize,-,1),merge(mergedList,i,i+len,-,1,CurrentSize,-,1),;,else for,(,int,j=i,;,j=CurrentSize,-,1,;,j+),mergedList.Vectorj=Vectorj,;,迭代的归并排序算法,21,25,25*,25*,93,62,72,08,37,16,54,49,21,25,49,62,93,08,72,16,37,54,21,25,25*,49,08,62,72,93,16,37,54,08,08,21,16,25,21,25*,25,49,25*,62,37,72,49,93,54,16,37,54,62,72,93,len,=1,len,=2,len,=4,len,=8,len,=16,(两路)归并排序的主算法,template,void,dataList,:,MergeSort(),/,按对象排序码非递减的顺序对表中对象排序,dataList,tempList(MaxSize),;,int,len=1,;,while,(len CurrentSize),MergePass(tempList,len),;,len*=2,;,tempList,.,MergePass(,this,len),;,len*=2,;,在迭代的归并排序算法中,函数,MergePass(),做一趟两路归并排序,要调用,merge(),函数,n,/(2*len),O(,n,/len),次,函数,MergeSort(),调用,MergePass(),正好,log,2,n,次,而每次,merge(),要执行比较,O(len),次,所以算法总的时间复杂度为,O(,n,log,2,n,)。,归并排序占用附加存储较多,需要另外一个与原待排序对象数组同样大小的辅助数组。这是这个算法的缺点。,归并排序是一个,稳定,的排序方法。,