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

第7章排序——很常见的一类问题（并不局限于排序本身）§1预备知识voidX_Sort(ElementTypeA[],intN)/*N是排序元素个数，是合法的整数*//*为简单起见，假设数组只包含整数*//*‘’和‘’运算符存在，而且是仅有的允许对输入数据进行的操作*/基于比较的排序/*仅考虑内部排序*/整个排序工作能够在主存中完成§2插入排序voidInsertionSort(ElementTypeA[],intN){intj,P;ElementTypeTmp;for(P=1;PN;P++){Tmp=A[P];/*thenextcomingcard*/for(j=P;j0&&A[j-1]Tmp;j--)A[j]=A[j-1];/*shiftsortedcardstoprovideapositionforthenewcomingcard*/A[j]=Tmp;/*placethenewcardattheproperposition*/}/*endfor-P-loop*/}最坏情形:输入的A[]是反序的。T(N)=O(N2)最好情形:输入的A[]是已预先排序的。T(N)=O(N)§3一些简单排序算法的下界【定义】成员存数的数组的一个逆序是指数组中具有性质ij但A[i]A[j]的序偶（A[i]，A[j]）。〖例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(N1)/4.【定理】通过交换相邻元素进行排序的任何算法平均需要(N2)时间。§4希尔排序----byDonaldShell〖例2〗Sort:81941196123517952858417515962812588135419417751195155-sort964194112858357595128117153-sort1-sort96419411285835759512811715定义一个增量序列h1h2…ht(h1=1)分步骤进行“间隔hk-插入排序”，k=t,t-1,…,1Note:一个hk-排序的文件（此后将是hk1-排序的）保持它的hk-排序性。§4希尔排序希尔增量序列:ht=N/2,hk=hk+1/2voidShellsort(ElementTypeA[],intN){inti,j,Increment;ElementTypeTmp;for(Increment=N/2;Increment0;Increment/=2)/*hsequence*/for(i=Increment;iN;i++){/*insertionsort*/Tmp=A[i];for(j=i;j=Increment;j-=Increment)if(TmpA[j-Increment])A[j]=A[j-Increment];elsebreak;A[j]=Tmp;}/*endfor-Iandfor-Incrementloops*/}§4希尔排序最坏情形分析:【定理】使用希尔增量的希尔排序的最坏运行时间是(N2)。〖例3〗一个坏例子:19210311412513614715816192103114125136147158168-sort192103114125136147158164-sort192103114125136147158162-sort123456789101112131415161-sort增量对未必互素，因此较小的增量可能影响很小。§4希尔排序Hibbard增量序列:hk=2k1----相邻增量没有公因子。【定理】使用Hibbard增量的希尔排序的最坏情形运行时间为(N3/2).猜测：Tavg–Hibbard(N)=O(N5/4)Sedgewick的最好增量序列是{1,5,19,41,109,…}，该序列中的项要么是94i–92i+1，或者是4i–32i+1。猜测其平均运行时间Tavg(N)=O(N7/6)，最坏情形运行时间Tworst(N)=O(N4/3).希尔排序算法的整体时间复杂度和增量序列的选取有关，目前并没有统一的最优增量序列。希尔排序是算法非常简单但又具有极其复杂的分析的一种排序算法。它对适度的大量输入数据（万数量级）是经常选用的算法。§5堆排序Algorithm1:{BuildHeap(H);for(i=0;iN;i++)TmpH[i]=DeleteMin(H);for(i=0;iN;i++)H[i]=TmpH[i];}/*O(N)*//*O(logN)*//*O(1)*/T(N)=O(NlogN)空间要求翻倍。§5堆排序bdacA[0][1][2][3]dcbdbcbcaabbaAlgorithm2:voidHeapsort(ElementTypeA[],intN){inti;for(i=N/2;i=0;i--)/*BuildHeap*/PercDown(A,i,N);for(i=N-1;i0;i--){Swap(&A[0],&A[i]);/*DeleteMax*/PercDown(A,0,i);}}堆排序的数据从位置0开始。【定理】对N个互异项的随机排列进行堆排序，所用的比较平均次数为2NlogNO(NloglogN).Note:虽然堆排序有最好的平均情形时间，但实践中它比某个版本的使用Sedgewick增量序列的希尔排序要慢。§6归并排序1.合并两个已排序数组1132426215273812LposRposTposT(N)=O()，N是总的元素个数。NLposRposTposTpos二路归并。也可以使用多路归并。§6归并排序2.MergesortvoidMSort(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&&Rpos=RightEnd)/*mainloop*/if(A[Lpos]=A[Rpos])TmpArray[TmpPos++]=A[Lpos++];elseTmpArray[TmpPos++]=A[Rpos++];while(Lpos=LeftEnd)/*Copyrestoffirsthalf*/TmpArray[TmpPos++]=A[Lpos++];while(Rpos=RightEnd)/*Copyrestofsecondhalf*/TmpArray[TmpPos++]=A[Rpos++];for(i=0;iNumElements;i++,RightEnd--)/*CopyTmpArrayback*/A[RightEnd]=TmpArray[RightEnd];}§6归并排序3.分析T(1)=1T(N)=2T(N/2)+O(N)=2kT(N/2k)+k*O(N)=N*T(1)+logN*O(N)=O(N+NlogN)非递归实现:A0123…………n4n3n2n1…………………………………………Note:归并排序需要线性的额外存储,并且经常复制临时数组导致效率降低。它很少用于内部排序，然而在外部排序中非常常用。§7快速排序--实践中已知的最快排序算法1.算法voidQuicksort(ElementTypeA[],intN){if(N2)return;pivot=pickanyelementinA[];PartitionS={A[]\pivot}intotwodisjointsets:A1={aS|apivot}andA2={aS|apivot};A=Quicksort(A1,N1){pivot}Quicksort(A2,N2);}1381924365315726750134331572606581927501326314357657581920132631435765758192ThebestcaseT(N)=O()NlogN枢纽元放在合适的位置上，且不需要再移动。SN个元素S1N1个元素S2N2个元素元素=e元素eeS1’’S2’’元素=e2元素e2e2S1’S2’元素=e1e1元素e1枢纽元e枢纽元e2枢纽元e1递归思路§7快速排序2.选择枢纽元一种错误的方法:Pivot=A[0]最坏情形:A[]已经预排序–快速排序将花费O(N2)时间，却没干什么事一种安全的做法:Pivot=randomselectfromA[]随机数生成器的代价是昂贵的。三数中值分割法（Median-of-ThreePartitioning）:Pivot=median(left,center,right)消除了预排序的坏情形，且减少了快速排序约5%的运行时间。如果我们仔细地实现，算法并不太困难…如果一个元素=枢纽元，该怎么做?如果同时停止i和j，并进行交换呢？对下面的元素序列将发生什么呢：1,1,1,…,1?额哦，那将会造成大量的哑交换…但是嘿!至少这个序列将被分割成两个相等大小的子数组。非常好!那么另一种做法怎么样–i和j都不停止?没有交换…但是T(N)=…那么T(N)=O(N2)。所以我们最好同时停住i和j并进行额外的交换。§7快速排序3.分隔策略8149035276592869ijjiiijiiji§7快速排序4.小数组问题:对于很小的数组(N20)，快速排序比插入排序慢。解决办法:当N变小时设置截止范围(如N=10)，并使用其他有效的算法进行排序(如插入排序)。5.实现voidQuicksort(ElementTypeA[],intN){Qsort(A,0,N-1);/*A:thearray*//*0