第2章-分治策略3快速排序

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,06 十一月 2024,第2章 分治策略3快速排序,QuickSort,Select a,pivot,(partitioning element),Rearrange the list so that all the elements in the positions before the pivot are smaller than or equal to the pivot and those after the pivot are larger than the pivot,Exchange the pivot with the last element in the first(i.e.,sublist)the pivot is now in its final position,Sort the two sublists,2,2.5 快速排序问题,基本策略是：,将数组A1:n分解成两个子数组B1:p和Bp+1:n，使得B1:p中的元素均不大于Bp+1:n中的元素，然后分别对这里两个数组中的元素进行排序（非降的），最后再把两个排好序的数组接起来即可。,p,A,i,p,A,i,p,3,选取A的某个元素t=A(s)，然后将其他元素重新排列，使A(1:n)中所有在t以前出现的元素都小于或等于t，而在t之后出现的元素都大于或等于t。,A(1),A(2),A(s-1),A(s),A(s+1),A(n),t,划分元素,A(n),A(k),t,A(j),A(2),A(1),经过一次划分后,每个元素都小于或等于t,每个元素都大于或等于t,2.5 快速排序问题,4,The partition algorithm,5,算法步骤,分解(Divide):,以,a,p,为基准元素将,a,p,:,r,划分成3段,a,p,:,q,-1,a,q,和,a,q,+1:,r,使得,a,p,:,q,-1中任何一个小于等于,a,q,下标,q,在划分过程中确定。,递归求解(conquer):,通过递归调用快速排序算法分别对,a,p,:,q,-1和,a,q,+1:,r,进行排序。,合并(Merge):,由于对,a,p,:,q,-1和,a,q,+1:,r,的排序是就地进行的，所以在,a,p,:,q,-1和,a,q,+1:,r,都已排好的序后步需执行任何计算,a,p,:,r,就已排好序。,2.5快速排序问题,6,快速排序,template,void QuickSort(Type a,int p,int r),if(pr),int q=Partition(a,p,r);,QuickSort(a,p,q-1);/对左半段排序,QuickSort(a,q+1,r);/对右半段排序,a的起始位置,a的终止位置,Partition函数负责将a进行一次分割，返回分割元素的位置,快速排序问题,2.5快速排序问题,7,划分过程,Partition的过程中，首先要选择一个元素，根据其值划分数组。称该元素为中轴。,选择中轴有许多不同的策略，我们使用最简单的策略，选择第一个元素：s=ap。,快速排序问题,2.5快速排序问题,8,划分举例,(1),(2),(3),(4),(5),(6),(7),(8),(9),(10),i,p,65,70,75,80,85,60,55,50,45,+,2,9,65,45,75,80,85,60,55,50,70,+,3,8,65,45,50,80,85,60,55,75,70,+,4,7,65,45,50,55,85,60,80,75,70,+,5,6,65,45,50,55,60,85,80,75,70,+,6,5,60,45,50,55,65,85,80,75,70,+,快速排序问题,2.5快速排序问题,Figure,2-1,9,划分的过程,使用一种两次扫描子数组的方法:一次是,从左到右,另一次是,从右到左,每次都把子数组的元素和中轴进行比较。,从左到右的扫描,从第二个元素,开始,希望小于中轴的元素位于子数组的第一部分，扫描会忽略小于中轴的元素，,直到遇到第一个大于等于中轴的元素才会停止,。,从右到左的扫描从,最后一个元素,开始，因为我们希望大于中轴的元素位于子数组的第二部分，扫描会忽略大于中轴的元素，,直到遇到第一个小于等于中轴的元素才会停止。,快速排序问题,2.5快速排序问题,10,P,全部=p,=p,i,j,全部=p,=p,全部=p,=p,=p,全部=p,P,i,j,快速排序问题,如果扫描指针i和j不相交，ij,把中轴和Aj交换，得到该数组的一个分区。,如果扫描指针i指向同一元素，ij，被指向元素的值一定等于p。,2.5快速排序问题,11,划分程序,template,int Partition(Type a,int p,int r),int i=,j=,;,Type x=,;,while(true),while(,a+i x,);,if(,)break;,Swap(a i,a j );,a p =,;,a j =,;,return j;,快速排序问题,p,r+1,a p,i=j,a j,x,左侧扫描指针起始,右侧扫描指针起始,中轴元素,移动左侧扫描指针,移动右侧扫描指针,2.5快速排序问题,该算法是否有问题？,12,快速排序问题,例：排列 5，3，1，9，8，2，4，7,0 1 2 3 4 5 6 7,i j,5,3 1 9 8 2 4 7,i j,5,3 1 9 8 2 4 7,i j,5,3 1 4 8 2 9 7,i j,5,3 1 4 8 2 9 7,i j,5,3 1 4 2 8 9 7,j i,5,3 1 4 2 8 9 7,2,3 1 4,5,8 9 7,i j,2,3 1 4,i j,2,3 1 4,i j,2,1 3 4,j i,2,1 3 4,1,2,3 4,1,i j,3,4,j i,3,4,4,i j,8,9 7,j i,8,7 9,7,8,9,7,9,2.5快速排序问题,13,问题：,扫描停止的时候i和j有几种关系，每种代表哪种情况？,下标i和j会不会超出a的下标界？,该排序算法是否稳定？,快速排序问题,2.5快速排序问题,14,Efficiency of QuickSort,Best case,:split in the middle,(,n,log,n,),Worst case,:sorted array!(,n,2,),Average case,:random arrays,(,n,log,n,),Improvements:,better pivot selection:median of three partitioning avoids worst case in sorted files,switch to insertion sort on small subfiles,elimination of recursion,these combine to 20-25%improvement,Considered the method of choice for internal sorting for large files(,n,10000),15,算法分析,最坏情况：划分的两个区域分别包含n-1个元素和1个元素，也就是已经排好序的数组。如果用A0作为中轴，从左到右的扫描会停在A1上，而从右到左的扫描会一直处理到A0，导致分裂点出现在0这个位置，所以，在进行了n1次比较之后建立了分区，并且将A0 和它本身进行了交换以后，快速排序算法还会对严格递增的数组A1n-1进行排序，对规模减小了的严格递增数组的排序会一直继续到最后一个子数组An-2n-1，这种情况下，键值比较的总次数应该等于：,(n+1)+n+3=O(n,2,),快速排序问题,2.5快速排序问题,16,算法分析,最坏情况：划分的两个区域分别包含,n,1个元素和1个元素，如果每一步都出现这种情况，其复杂性,T,(,n,),O,(1),n,1,T,(,n,)=,T,(,n,-1)+,O,(,n,),n,1,解得：,T,(,n,)=,O,(,n,2,),快速排序问题,2.5快速排序问题,17,最好情况:每次划分所取的基准都恰好为中值，即每次划分都产生两个大小为n/2的区域，,O(1)n1,T(n)=,2T(n/2)+O(n)n1,T(n)=O(nlogn),快速排序问题,2.5快速排序问题,18,计数排序、冒泡排序、插入排序、选择排序、归并排序和快速排序的时间复杂性如下：,算法 最坏复杂性 平均复杂性,冒泡排序 n,2,n,2,计数排序 n,2,n,2,插入排序 n,2,n,2,选择排序 n,2,n,2,快速排序 n,2,n log n,归并排序 n log n n log n,快速排序问题,2.5快速排序问题,19,2.6 线性时间选择 Selection in Linear Time,问题：,已知n元数组A1:n，试确定其中第k小的元素。,如果k1，就是找最小的元素，如果kn，就是找最大的元素。,2.6 线性时间选择,20,利用快速分类思想解决这一问题,根据PARTITION过程。如果划分元素v确定在A(j)的位置上，则有j-1个元素小于或等于A(j)，且有n-j个元素大于或等于A(j)。,2.6 线性时间选择,21,假设在一次划分中，划分元素v处于第j个位置。,如果kj，则要找的第k小元素在新数组Aj1:n中,而且是Aj1:n的第k-j小元素。,2.6 线性时间选择,22,采用划分的选择算法,若,k=j,，则A(j)即是第k小元素；否则，,若,kj,，则第k小元素为A(j+1:n)中第k-j小元素。,A(1),A(2),A(j-1),A(j),A(j+1),A(n-1),A(n),V,划分元素,kj时，第k小元素所在的集合,K=j时，第k小元素就是划分元素,2.6 线性时间选择,23,template,Type RandomizedSelect(Type a,int p,int r,int k),if(p=r),return a p;,int i=RandomizedPartition(a,p,r);,j=i-p+1;,if(k 3，调用RandomizedSelect(a,4,9,2),第二次调用Randomizedpartition(a,4,9)=6,得到,2 1,4,8 7,9,12 10 15,56，调用RandomizedSelect(a,4,6,2),第二次调用Randomizedpartition(a,4,6)=5,得到,2 1,4,7,8,9,12 10 15,2.6 线性时间选择,25,算法复杂度：,在最坏情况下，总是在最大元素处划分，算法,RandomizedSelect,需要O(n,2,)计算时间。,但可以证明，算法,RandomizedSelect,可以在O(n)平均时间内找出n个输入元素中的第k小元素。,2.6 线性时间选择,26,如果能在线性时间内找到一个划分基准，使得按这个基准所划分出的2个子数组的长度都至少为原数组长度的倍(01是某个正常数)，那么就可以,在最坏情况下,用O(n)时间完成选择任务。,例如，若=9/10，算法递归调用所产生的子数组的长度至少缩短1/10。所以，在最坏情况下，算法所需的计算时间T(n)满足递归式T(n)T(9n/10)+O(n)。由此可得T(n)=O(n)。,2.6 线性时间选择,27,将n个输入元素划分成n/5个组，每组5个元素，只可能有一个组不是5个元素。用任意一种排序算法，将每组中的元素排好序，并取出每组的中位数，共n/5个。,递归调用,select,来找出这,n/5,个元素的中位数。如果,n/5,是偶数，就找它的,2个中位数中较大的一个。以这个元素作为划分基准。,设所有元素互不相同。在这种情况下，找出的基准x至少比3(n-5)/10个元素大，因为在每一组中有2个元素小于本组的中位数，而n