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

.第7章排序，中常见的问题(不局限于排序本身)、1初步知识，voidX_Sort(ElementTypeA、intN )、/*N是排序元素的数目，是合法的整数*/*，因此该阵列不存在整数*/、/* 、运算符只考虑允许对输入数据进行操作的*/基于比较的排序、/*内部排序*/，可以在主内存中完成整个排序工作。 插入、双排序、voidinsertisorting (elementtypea 、intN)intj，p； ElementTypeTmp； for(P=1； P0/* ppppporthewcardattheproperposition */* end for-p-loop */，最坏情况为：输入的A为反序。 T(N)=O(N2)，最佳情况：输入A预先排序。 T(N)=O(N )，3个简单排序算法的下界，【定义】成员数的阵列的一个逆序是指数组中具有性质iAj的偶数(Ai、Aj )。 22222222222222222222222222222652、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 .【定理】通过交换邻接元素进行排序的算法需要平均(n-2 )时间。 4希尔排序- -定义bydonaldshell、5-sort、3-sort、1-sort和增量序列h1 0;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(Left,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-路合并；趟，.,多项合并，例怎样只使用3个磁盘驱动器完成2路合并？,如果顺串的个数是一个斐波那契数FN,那么分配这些顺串的最好的方式是把它们分裂成两