湘潭大学 数据结构 Ch07 Sorting 排序算法

.,第7章排序,很常见的一类问题（并不局限于排序本身）,.,1预备知识,voidX_Sort(ElementTypeA,intN),/*N是排序元素个数，是合法的整数*/,/*为简单起见，假设数组只包含整数*/,/*和运算符存在，而且是仅有的允许对输入数据进行的操作*/,基于比较的排序,/*仅考虑内部排序*/,整个排序工作能够在主存中完成,.,2插入排序,voidInsertionSort(ElementTypeA,intN)intj,P;ElementTypeTmp;for(P=1;P0/*placethenewcardattheproperposition*/*endfor-P-loop*/,最坏情形:,输入的A是反序的。T(N)=O(N2),最好情形:,输入的A是已预先排序的。T(N)=O(N),.,3一些简单排序算法的下界,【定义】成员存数的数组的一个逆序是指数组中具有性质iAj的序偶（Ai，Aj）。,例1输入数据34,8,64,51,32,21有个逆序。,9,(34,8)(34,32)(34,21)(64,51)(64,32)(64,21)(51,32)(51,21)(32,21),在插入排序中恰好需要执行次交换。,9,交换两个不按原序排列的相邻元素恰好消除一个逆序。,T(N,I)=O()，I是初始数组中的逆序数。,I+N,如果数组几乎有序，这个时间是很快的。,.,这就是全部结论?那么怎么加速排序?,嘿!我们讨论的是基于比较的排序，你必须进行比较，然后呢？,这个定理告诉我们什么?,聪明!为了使算法运行更快，我们必须在一次交换中不止消除一个逆序。,交换距离较远的元素？,呃散列?,对一整类只交换相邻元素的算法来说，都需要花费O(N2)的时间来排序。,3一些简单排序算法的下界,【定理】N个互异数的数组的平均逆序数是N(N1)/4.,【定理】通过交换相邻元素进行排序的任何算法平均需要(N2)时间。,.,4希尔排序-byDonaldShell,5-sort,3-sort,1-sort,定义一个增量序列h1h20;Increment/=2)/*hsequence*/for(i=Increment;i=Increment;j-=Increment)if(TmpAj-Increment)Aj=Aj-Increment;elsebreak;Aj=Tmp;/*endfor-Iandfor-Incrementloops*/,.,4希尔排序,最坏情形分析:,【定理】使用希尔增量的希尔排序的最坏运行时间是(N2)。,8-sort,4-sort,2-sort,1-sort,.,4希尔排序,Hibbard增量序列:,hk=2k1-相邻增量没有公因子。,【定理】使用Hibbard增量的希尔排序的最坏情形运行时间为(N3/2).,猜测：,TavgHibbard(N)=O(N5/4),Sedgewick的最好增量序列是1,5,19,41,109,，该序列中的项要么是94i92i+1，或者是4i32i+1。猜测其平均运行时间Tavg(N)=O(N7/6)，最坏情形运行时间Tworst(N)=O(N4/3).,.,希尔排序算法的整体时间复杂度和增量序列的选取有关，目前并没有统一的最优增量序列。希尔排序是算法非常简单但又具有极其复杂的分析的一种排序算法。它对适度的大量输入数据（万数量级）是经常选用的算法。,.,5堆排序,Algorithm1:BuildHeap(H);for(i=0;i0;i-)Swap(,堆排序的数据从位置0开始。,【定理】对N个互异项的随机排列进行堆排序，所用的比较平均次数为2NlogNO(NloglogN).,Note:虽然堆排序有最好的平均情形时间，但实践中它比某个版本的使用Sedgewick增量序列的希尔排序要慢。,.,6归并排序,1.合并两个已排序数组,1,2,Lpos,Rpos,Tpos,T(N)=O()，N是总的元素个数。,N,Lpos,Rpos,Tpos,Tpos,二路归并。也可以使用多路归并。,.,6归并排序,2.Mergesort,voidMSort(ElementTypeA,ElementTypeTmpArray,intLeft,intRight)intCenter;if(LeftRight)/*ifthereareelementstobesorted*/Center=(Left+Right)/2;MSort(A,TmpArray,Left,Center);/*T(N/2)*/MSort(A,TmpArray,Center+1,Right);/*T(N/2)*/Merge(A,TmpArray,Left,Center+1,Right);/*O(N)*/voidMergesort(ElementTypeA,intN)ElementType*TmpArray;/*needO(N)extraspace*/TmpArray=malloc(N*sizeof(ElementType);if(TmpArray!=NULL)MSort(A,TmpArray,0,N-1);free(TmpArray);elseFatalError(Nospacefortmparray!);,如果TmpA定义成Merge的局部变量，则每次调用Merge都需要开辟不同的空间,那么S(N)=O(),NlogN,.,6归并排序,/*Lpos=startoflefthalf,Rpos=startofrighthalf*/voidMerge(ElementTypeA,ElementTypeTmpArray,intLpos,intRpos,intRightEnd)inti,LeftEnd,NumElements,TmpPos;LeftEnd=Rpos-1;TmpPos=Lpos;NumElements=RightEnd-Lpos+1;while(Lpos=LeftEnd,.,6归并排序,3.分析,T(1)=1,T(N)=2T(N/2)+O(N),=2kT(N/2k)+k*O(N),=N*T(1)+logN*O(N),=O(N+NlogN),非递归实现:,Note:归并排序需要线性的额外存储,并且经常复制临时数组导致效率降低。它很少用于内部排序，然而在外部排序中非常常用。,.,7快速排序,-实践中已知的最快排序算法,1.算法,voidQuicksort(ElementTypeA,intN)if(N,j,i,i,j,i,i,j,i,ACenter)Swap(/*Returnpivot*/,.,7快速排序,voidQsort(ElementTypeA,intLeft,intRight)inti,j;ElementTypePivot;if(Left+CutoffPivot)/*scanfromright*/if(iN将会怎样?,“基数排序(RadixSort)”是“桶排序(BucketSort)”的推广。,10基数排序,.,基数排序：一般用于多关键字的排序,10基数排序,例一叠牌的排序要基于两个关键字。,基数排序的方法一般采用“主位优先法”(MostSignificantDigitFirst,MSD)或者“次位优先法”(LeastSignificantDigitFirst,LSD),相当于“分治法”,“分配-收集”法,.,主位优先法(MSD)排序,先排花色:比如,建立4个花色的“桶”,再排面值:每个桶分别独立排序(可以采用以前介绍的任何排序方法),10基数排序,.,先排面值:建立13个面值的“桶”，把牌放入相应的桶中（这叫“分配”）；,依次“收集”它们成为一叠牌；,再排花色:建立4个桶进行再“分配”；,次位优先法(LSD)排序,再次“收集”它们成为一叠牌即告完成。,10基数排序,还不赶紧拿一副牌出来试试？,.,例给定N=10个整数，范围介于0到999(M=1000)之间。是否可以在线性的时间内把它们排序?,单关键字的基数排序,输入:64,8,216,512,27,729,0,1,343,125,（3位数可以看成个3关键字，再按“次位优先法”排序）,0,1,512,343,64,125,216,27,8,729,0,1,8,512,216,125,27,729,343,64,输出:0,1,8,27,64,125,216,343,512,729,时间复杂性：T=O(D(N+R)其中D是轮次,N是元素个数,R是桶的数量.,按“主位优先法”排序将会怎样?,10基数排序,空间复杂性：S=O(N+R),N是元素个数,R是桶的数量.,用链式储存更便于分配与收集？,.,11外部排序*,11外部排序*(ExternalSorting),内部排序和外部排序,分两个步实施：(a)分段内排序(b)归并（二路或多路）,要提高外排的效率，关键要解决以下4个问题：如何减少归并轮数；如何有效安排内存中的输入、输出块，使得机器的并行处理能力被最大限度地利用；如何有效生成归并段；如何将归并段进行有效归并。,.,外部排序模型,模型假设至少3个磁带驱动器进行排序工作。其中2个执行有效的排序，而第3个驱动器进行简化工作。,简单算法,使用归并排序的合并算法趟，外加一趟构造初始顺串。,多路合并,有额外的磁带：2-路合并扩充为k