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

12.5快速排序问题QuickSort由著名计算机科学家霍尔(C.A.R.Hoare)给出。把原序列分成两个子问题，在被分成的两个子问题以后不再需要归并。被分成的两个子问题必须满足一子问题中的所有元素都小于或等于另一子问题的任何一个元素。2QuickSortSelectapivot(partitioningelement)RearrangethelistsothatalltheelementsinthepositionsbeforethepivotaresmallerthanorequaltothepivotandthoseafterthepivotarelargerthanthepivotExchangethepivotwiththelastelementinthefirst(i.e.,≤sublist)–thepivotisnowinitsfinalpositionSortthetwosublists32.5快速排序问题基本策略是：将数组A[1:n]分解成两个子数组B[1:p]和B[p+1:n]，使得B[1:p]中的元素均不大于B[p+1:n]中的元素，然后分别对这里两个数组中的元素进行排序（非降的），最后再把两个排好序的数组接起来即可。pA[i]≤pA[i]p4选取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)tA(j)…A(2)A(1)经过一次划分后每个元素都小于或等于t每个元素都大于或等于t2.5快速排序问题5Thepartitionalgorithm6算法步骤分解(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快速排序问题7快速排序templateclassTypevoidQuickSort(Typea[],intp,intr){if(pr){intq=Partition(a,p,r);QuickSort(a,p,q-1);//对左半段排序QuickSort(a,q+1,r);//对右半段排序}}a的起始位置a的终止位置Partition函数负责将a进行一次分割，返回分割元素的位置快速排序问题2.5快速排序问题8划分过程Partition的过程中，首先要选择一个元素，根据其值划分数组。称该元素为中轴。选择中轴有许多不同的策略，我们使用最简单的策略，选择第一个元素：s=a[p]。快速排序问题2.5快速排序问题9划分举例(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)ip657075808560555045+∞29654575808560555070+∞38654550808560557570+∞47654550558560807570+∞56654550556085807570+∞65604550556585807570+∞快速排序问题2.5快速排序问题Figure2-110划分的过程使用一种两次扫描子数组的方法:一次是从左到右,另一次是从右到左,每次都把子数组的元素和中轴进行比较。从左到右的扫描从第二个元素开始,希望小于中轴的元素位于子数组的第一部分，扫描会忽略小于中轴的元素，直到遇到第一个大于等于中轴的元素才会停止。从右到左的扫描从最后一个元素开始，因为我们希望大于中轴的元素位于子数组的第二部分，扫描会忽略大于中轴的元素，直到遇到第一个小于等于中轴的元素才会停止。快速排序问题2.5快速排序问题11P全部=p=p·····=p全部=pij全部=p=p全部=pPi=j全部=p=p=p全部=pPij快速排序问题如果扫描指针i和j不相交，ij,简单交换A[i]和A[j]，再分别对i加1，j减1，然后继续扫描如果扫描指针i和j相交，ij,把中轴和A[j]交换，得到该数组的一个分区。如果扫描指针i指向同一元素，i＝j，被指向元素的值一定等于p。2.5快速排序问题12划分程序templateclassTypeintPartition(Typea[],intp,intr){inti=,j=;Typex=;while(true){while(a[++i]x);while(a[--j]x);if()break;Swap(a[i],a[j]);}a[p]=;a[j]=;returnj;}快速排序问题pr+1a[p]i=ja[j]x左侧扫描指针起始右侧扫描指针起始中轴元素移动左侧扫描指针移动右侧扫描指针2.5快速排序问题该算法是否有问题？13快速排序问题例：排列5，3，1，9，8，2，4，701234567ij53198247ij53198247ij53148297ij53148297ij53142897ji5314289723145897ij2314ij2314ij2134ji213412341ij34ji344ij897ji879789792.5快速排序问题14问题：扫描停止的时候i和j有几种关系，每种代表哪种情况？下标i和j会不会超出a的下标界？该排序算法是否稳定？快速排序问题2.5快速排序问题15EfficiencyofQuickSortBestcase:splitinthemiddle—Θ(nlogn)Worstcase:sortedarray!—Θ(n2)Averagecase:randomarrays—Θ(nlogn)Improvements:betterpivotselection:medianofthreepartitioningavoidsworstcaseinsortedfilesswitchtoinsertionsortonsmallsubfileseliminationofrecursionthesecombineto20-25%improvementConsideredthemethodofchoiceforinternalsortingforlargefiles(n≥10000)16算法分析最坏情况：划分的两个区域分别包含n-1个元素和1个元素，也就是已经排好序的数组。如果用A[0]作为中轴，从左到右的扫描会停在A[1]上，而从右到左的扫描会一直处理到A[0]，导致分裂点出现在0这个位置，所以，在进行了n＋1次比较之后建立了分区，并且将A[0]和它本身进行了交换以后，快速排序算法还会对严格递增的数组A[1···n-1]进行排序，对规模减小了的严格递增数组的排序会一直继续到最后一个子数组A[n-2···n-1]，这种情况下，键值比较的总次数应该等于：(n+1)+n+…+3=O(n2)快速排序问题2.5快速排序问题17算法分析最坏情况：划分的两个区域分别包含n－1个元素和1个元素，如果每一步都出现这种情况，其复杂性T(n)O(1)n≤1T(n)=T(n-1)+O(n)n1解得：T(n)=O(n2)快速排序问题2.5快速排序问题18最好情况:每次划分所取的基准都恰好为中值，即每次划分都产生两个大小为n/2的区域，O(1)n≤1T(n)=2T(n/2)+O(n)n1T(n)=O(nlogn)快速排序问题2.5快速排序问题19计数排序、冒泡排序、插入排序、选择排序、归并排序和快速排序的时间复杂性如下：算法最坏复杂性平均复杂性冒泡排序n2n2计数排序n2n2插入排序n2n2选择排序n2n2快速排序n2nlogn归并排序nlognnlogn快速排序问题2.5快速排序问题202.6线性时间选择SelectioninLinearTime问题：已知n元数组A[1:n]，试确定其中第k小的元素。如果k＝1，就是找最小的元素，如果k＝n，就是找最大的元素。2.6线性时间选择21利用快速分类思想解决这一问题根据PARTITION过程。如果划分元素v确定在A(j)的位置上，则有j-1个元素小于或等于A(j)，且有n-j个元素大于或等于A(j)。2.6线性时间选择22假设在一次划分中，划分元素v处于第j个位置。如果kj，则要找的第k小元素在新数组A[1:j-1]中，而且是A[1:j-1]的第k小元素；如果k＝j，则划分元素v即是要找的第k小元素；如果kj，则要找的第k小元素在新数组A[j＋1:n]中,而且是A[j＋1:n]的第k-j小元素。2.6线性时间选择23采用划分的选择算法若k=j，则A(j)即是第k小元素；否则，若kj，则第k小元素为A(1:j-1)中第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小元素所在的集合Kj时，第k小元素所在的集合K=j时，第k小元素就是划分元素2.6线性时间选择24templateclassTypeTypeRandomizedSelect(Typea[],intp,intr,intk){if(p==r)returna[p];inti=RandomizedPartition(a,p,r);j=i-p+1;if(k=j)returnRandomizedSelect(a,p,i,k);elsereturnRandomizedSelect(a,i+1,r,k-j);}2.6线性时间选择25例：4，1，10，9，7，12，8，2，15中寻找第5个最小元素，假设下标从1到9第一次调用Randomizedpartition(a,1,9)=3得到21497128101553，调用RandomizedSelect(a,4,9,2)第二次调用Randomizedpartition(a,4,9)=6得到21487912101556，调用RandomizedSelect(a,4,6,2)第二次调用Randomizedpartition(a,4,6)=5得到2147891210152.6线性时间选择26算法复杂度：在最坏情况下，总是在最大元素处划分，算法RandomizedSelect需要O(n2)计算时间。但可以证明，算法RandomizedSelect可以在O(n)平均时间内找出n个输入元素中的第k小元素。2.6线性时间选择27如果能在线性时间内找到一个划分基准，使得按这个基准所划分出的2个子数组的长度都至少为原数组长度的ε倍(0ε1是某个正常数)，那么就可以在最坏情况下用O(n)时间完成选择任务。例如，若ε=9/10，算法递归调用所产生的子数组的长度至少缩短1/10。所以，在最坏情况下，算法所需的计算时间T(n)满足递归式T(n)≤T(9n/10)+O(n)。由此可得T(n)=O(n)。2.6线性时间选择28将n个输入元素划分成n/5个组，每组5个元素，只可能有一个组不是5个元素。用任意一种排序算法，将每组中的元素排好序，并取出每组的中位数，共n/5个。递归调用select来找出这n/5个元素的中位数。如果n/5是偶数，就找它的2个中位数中较大的一个。以这个元素作为划分基准。设所有元素互不相同。在这种情况下，找出的基准x至少比3(n-5)/10个元素大，因为在每一组中有2个元素小于本组的中位数，而n/5个中位数中又有(n-5)/10个小于基准x。同理，基准x也至少比3(n-5)/10个元素小。而当n≥75时，3(n-5)/10≥n/4所以按此基准划分所得的2个子数组的长度都至少缩短1/4。2.6线性时间选择29priv