chapter2 Sorting算法与算法的分析技术.ppt

1,计算机算法设计与分析导论,刘璟,2,Chapter2.Sorting算法与算法的分析技术,2.1排序(Sorting)问题2.2O(n2)阶的排序算法2.3基于相邻元比较的排序算法和希尔(Shell)排序2.4O(nlogn)阶的排序算法2.5比较排序算法的时间复杂度下界2.6排序算法的有关研究,3,2.1排序（Sorting）问题,有关排序的几个基本概念：1.全序集：数据集合D称为关于关系“”的全序集，如果满足1ab，a=b，ba三者必居其一；2ab，bc，则ac。全体整数集、实数集、字符串集等都是全序集。2.排序（Sorting）问题：已知：n项记录R1，R2，Rn，其一个域称为关键字（Key），关键字值K1，K2，Kn属于一全序集。要求：重排n项记录为R(1)，R(2)，R(n)，其中：(1)，(2)，(n)，为1,n的一个排列，使对应的关键字满足：K(1)K(2)K(n)。,4,3.稳定（Stable）排序算法：如果排序问题满足：若R(i)=R(j)且ij则(i)0为一常数。证明方法1：采用归纳法当n=1时，A(n)=0，cnlnn=0，命题成立；假设当1kn，A(K)cklnk成立；由公式2.4.1和假设得：根据积分的性质：,28,于是，当n1取c=2时，A(n)2nlnn成立。推论2.3在输入序列的不同排序均匀分布的假设条件下，算法QuickSort的平均数据比较次数为:证明方法2：为了简化关于A(n)的递归方程，由,29,推出：为了消除过多的A(i)项，计算nA(n)-(n-1)A(n-1)：即令则有：,30,这是一个较为简单的递归方程，不难得到：由Harmonic级数，为Euler常数，得：,31,由此可以得到A(n)的更准确的表达式：5.空间复杂度分析：单从划分算法来看，QuickSort除有限的工作单元外，不占用额外的空间，但在递归过程中，待排序段的首元和尾元下标需要保存，在最坏情形可能递归n1次。因此，QuickSort在最坏情形下需要的空间代价为S(n)=(n)。,32,6.关于QuickSort算法的几点讨论：1）在最重要的性能，即平均时间代价上优于其它算法。当n比较大时，一般运行确实很快，因此被广泛采用。2）改善划分元的选取，可能产生更好的效果。常见的几种划分元的选取方法是：在first,last中取随机数i，以Li代替L1；在first,last中，取中间值i=int(first+last)/2)；取first，last，int（first+last）/2）三者的中值为划分元下标。3）算法的核心是划分。不同的划分策略会影响到移动次数。4）QuickSort采用递归算法的形式，简明但运行时在时间和空间上开销较大。一种改进方法是使用由用户设计的栈取代递归。算法2.8快速排序的改进算法QStackSort,33,5）空间复杂度的改进：快速排序算法的额外空间需求与递归和栈有关。当把两次递归调用改为单侧进栈，可以改进空间复杂度。当输入为升序（已排序）时，共需n1次进栈，占用O(n)空间。如果在程序中，每进行一次划分以后，就对f,i-1,i+1,l两段进行比较，把较大的一半进栈，先计算（划分）较小的一半，其内层循环次数（即栈的长度）必然小于logn，因此空间代价可降为O(logn)。6）快速排序算法对于较小的n，其性能不及插入算法。因此，可以设计一种综合算法，当输入序列长度小于某个固定值（例如n0=50）时，改用InsertSort进行排序。7）快速排序的最坏情形时间复杂度和额外空间代价，无论如何改进，总是它的缺点和不足。,34,2.4.2合并排序算法MergeSort1.算法的思路：把序列分为两部分，分别递归（排序）后，再把两个有序序列合并为一个有序序列。如Fig.2.4。,35,2.有序序列的合并算法：算法2.9有序序列的合并算法Merge3.合并排序算法MergeSort：算法2.10合并排序算法MergeSort4.算法的复杂度分析：该算法对两个长度为m的有序序列的合并，在最坏情形下至少需要2m1次比较。算法在最坏情形下的比较次数可用递归方程表示：（公式2.4.2）,36,忽略n为奇数的情形，由主项定理可得。假定n=2k（k为正整数），则公式2.4.2可以简化为：直接推导得：该算法平均情形比较次数A(n)=(nlogn)。其空间代价较大，需要大小为O(n)的额外空间。该算法是不稳定的。,37,5.关于合并排序算法的讨论：1）对于时间复杂度而言，在最坏情形下大大优于快速排序，但在平均情况下不一定优于快速排序。数据的移动次数也会对时间性能有所影响。2）可以比较容易地改写成非递归程序。3）合并排序的一种改进方法是充分利用输入序列中可能的已排序部分。算法2.11合并排序改进算法IIMergeSort2例如，输入序列为（4，12，8，6，0，11，27，5，20），实际上是4个有序串：（4，12），（8），（6，11，27），（5，20）。第一趟扫描合并为：（4，8，12），（5，6，9，11，20，27），第二趟扫描就已排好序。这个算法在在最好情形下的比较次数为B(n)=n1。,38,4）主要缺点是空间代价较大，每次合并操作都需要与待合并的数据等长的额外空间，其额外空间代价为O(n)阶。5）适合于并行计算。2.4.3堆排序算法HeapSort1.堆排序算法的思路：,如Fig.2.5，算法把待排序的数组L1.n视为一个二叉树，数组元素依次按广度第一的顺序与二叉树的结点相对应。结点间的链接利用下标来计算。对于结点i，如果2in，则i为叶结点，否则，2i为其左儿子下标，2i+1为其右儿子下标。,39,这样的二叉树的所有的叶结点位于树的最底层即d层或d1层，在最底层的叶结点位于左端。算法由两部分组成，第一部分称为建堆（BuildingHeap），就是通过数据的比较和移动，使得二叉树上每个内部节点的值大于其左、右子结点的值。这样的二叉树称为堆（Heap），如Fig.2.6所示。,40,第二部分称为根删除堆修复（DeleteFix）过程，如Fig.2.7，可以描述为：for(i=n;i=2;i-)Swap(L1,Li);FixHeap(L1.i-1);堆的修复过程，就是每次把两个儿子中的较大者上升，直到元素Li降到适当的位置为止。这一DeleteFix过程至多重复n次，每次修复所需的比较次数不会大于树高，而平衡二叉树的高不会大于logn（n为结点数），故此算法应有较好的性能。2.算法的描述：算法2.12堆排序算法HeapSort,41,42,3.算法的分析：令n=2d1且n/2nn，并把建堆过程写成递归形式：voidBHeap(H)BHeap(Hleft);BHeap(Hright);FixHeap(L,n,root,Lroot);return;它与函数BuildHeap是等价的。由于FixHeap(L,n,root,Lroot)的比较次数为2logn，故有：,43,根据主项定理：因为b=2，c=2，取=0.1，有故因此，建堆过程在最坏情形下的时间复杂度为线性阶。对于算法的第二部分，因为对于有k个结点的堆进行修复，至多需要次比较，即全部比较次数至多为：,44,定理2.4HeapSort在最坏情形下的数据比较次数为W(n)=2nlogn+O(n)，即HeapSort是一个(nlogn)阶的排序算法。HeapSort在平均情形下的比较次数是O(nlogn)。它是一个原址排序算法。4.堆排序算法的缺点：1）当输入序列为有序或几乎有序时，堆排序算法根本没有利用序列有序的条件，需要(nlogn)次比较，与最坏情形相比几乎没有改进。2）堆排序大约需要2*nlogn次比较，在大多数情况下，比快速排序和合并排序要慢。5.加速堆排序算法AHeapSort：在原来的FixHeap算法中，每一次需要做两次比较，即：if(Lvac*2Lvac*2+1)和if(kLlarger)。改进后的AFixHeap算法，每一步只做一次比较。,45,算法2.13改进的堆恢复过程AfixHeap在大多数情况下，第一个循环把空位移至叶结点，共用logn次比较，而向上的移动次数则很少。结点的比较次数在最坏情形下仍为2logn，但在大多数情况下则接近（大于）logn。如Fig.2.9所示。,46,为了把最坏情形下的比较次数由2nlogn缩小到nlogn，进一步改进的思路描述如下：设堆的高度为，空位的移动分为下移和上移，每下移、上移一层需要一次比较。开始时空位在顶点，设待插入元素的最终应插入的位置在h层，0hH。1m=H/2；2空位下移m层，共用m次比较；3if(Lvac/2n!。,60,引理2.9在所有具有l个叶结点的判定树中，若某棵树的epl最小，则这个DT的所有叶结点是平衡的，即它的叶结点之多分布在树的最下面两层。如Fig.2.14。证明：设判定树有叶结点X位于k层，kd1。因DT有d层，故必有叶结点Z1，Z2在d层，其父结点Y在d1层。,61,对判定树DT做一小的调整，把叶结点Z1，Z2从父结点Y上摘下，挂到结点X上（如Fig.2.15）。显然它仍然是一个有l个叶结点的判定树DT，但外部路长epl发生了变化。具体地说有三条路长发生了变化：在DT上，从根到X，Z1，Z2的三条路长为k+2d。在DT上，从根到Z1，Z2，Y的三条路长为2(k+1)+d-1=2k+d+1。因kd1，所以2k+d+1temp)Lj+1=Lj;elseLj+1=temp;break;return;,返回,68,算法2.3起泡排序算法BubbleSort,templatevoidBubbleSort(KeyL,intn)inti,j;for(i=1;ii;j-)if(LjLj-1)Swap(Lj,Lj-1);return;,返回,69,算法2.4起泡排序的改进算法BSort,templatevoidBSort(KeyL,intn)intp=1;inti,j;for(i=1;(ii;j-)p=0;if(Lj=1;s-,h=hs)for(intk=1;ktemp),返回,71,算法2.6快速排序算法QuickSort,templatevoidQuickSort(KeyL,intfirst,intlast)if(firstlast)intsplit=Partition(L,first,last);QuickSort(L,first,split1);QuickSort(L,split+1,last);return;,返回,72,算法2.7快速排序的划分算法Partition,templateintPartition(KeyL,intfirst,intlast)intleft=first;intright=last;Keypivot=Lfirst;while(left=pivot)right-;Lleft+=Lright;while(Lleftpivot)left+;Lright-=Lleft;Lleft=pivot;returnleft;,返回,73,算法2.8快速排序的改进算法QStackSort,templatevoidQStackSort(KeyL,intn)intf,l,i;stack.push(1,n);while(!stack.empty)stack.pop(f,l);while(fl)i=Partition(L,f,l);Stack.push(i+1,l);l=i1;return;,返回,74,算法2.9有序序列的合并算法Merge,templatevoidMerge(KeyS,intl,intm,intr)KeyT;inti=l;intj=m+1;intk=l;while(im)for(intp=j;p=r;p+)Tk+=Sp;elsefor(intp=i;p=m;p+)Tk+=Sp;for(p=l;pHsize)Lroot=k;elseif(2*root)=Hsize)intlarger=2*root;elseif(L2*rootL2*root+1)larger=2*root;/续下页,返回,78,算法2.12堆排序算法HeapSort,else/续上页larger=2*root+1;if(kLlarger)Lroot=k;elseLroot=Llarger;FixHeap(L,Hsize,larger,k);return;voidBuildHeap(ElementL,intn)for(inti=n/2;i=1;i-)FixHeap(L,n,i,Li);return;,返回,79,算法2.13改进的堆恢复过程AfixHeap,t