《算法导论》读书笔记附练习第七章快速排序

第七章快速排序Quicksortifp<rthenq_PABTITION(A,p,r)QUICKSORT^储q-1)1 QUICKSORT(A,q+l.r)快速排序是基于分治模式的：分解：数组工心」懈划分成两个(可能空)子数组川声一g—1]和*/+1",使得，小一1]中的每个元素都小于等于小],而且，小于等于/[十1中的元素。下标。也在返个划分过程中在行计算。解决：通过递归调用快速排序，对子数组的「q—1]和十1「而非序。合并：因为两个子数组使就地排序的，将它们的合并开需要操作：整个数组J小山已排序。数组划分：Partition(儿p,r)xA\r]ip-1forjptor-]doIfA[j}W£then01£+1exchange?![■;]HA[j]exchangeA[i+1]—A[r]return，+1在第3到6行中循环的每一轮迭代的开始，对伏何数组下标;，有：.如果则明”.如果।一」I，则明・...如果心『，则咽一证明：初始化：在循环的第一轮迭代前，有［p1和j 在户和尸间没有值，在,：+和j_］▼间也没有值。保持：在第四行中，如果/」］>」.，那么那加1,在渭加1后，条件2对..仃_1感立，并且其他性质保持开变；如果,4］］或「那么将j增加1，交换.［［*口门］，再将渭加L因为由亍了交换，现在有1团（一因而条件1满足。类似地迓有」［-1］>,,因为根据循环开变式，被交换在1］的项目是大于「的。终止：当终止时，j=,。于是，数组中的每个元素都在循环开变式所描述的三个集合的某一个▼中，亦即，我们已将数组中的所有元素划分成了三个集合：一个集合中包含了小于等于X的元素，第二个集合中包含了大于「的元素，迓有一个只包含了「的集合。在PH"/丁过程的最后两行中，通过将主元不最左的、大于「的元素在行交换，就将懒多动到了它在数组中间的位置上。此时，的输出满足分解步骤所做规定的要求。；…在▼数组上的运行时间为，-，其中「练习7.1-1W=<13,19,9、5.12,8,7,4,21,2,6.11>' ，."•「.，.1.0工二<9,5,8,19,12,13.7,4,21.2,641>।7.1-47.1-4:A=<9.5,8,7,4,13.19,12.21,2.6,11>A=<9,5,8,7,4,2.19,12.21,13.6,11>A=<9.5,8,7,4,2.0.12,21.13.19,11>A=<9,5,8,7,4,2.6.11,21.13.19,12>2:r—1修改：FARTITION(ap：r)xA[r]i—p-1forjptoV—1doifA[j]W工then+1exchangeA[i] A[7exctiaiig^A[i.+1]—A[rifi=r—1thenreturn出+rj/21()elsereturni+13:MAX:1-H1+[(r-1-p+1}f1]+[(r-1-^+11]x3+1+1,'V//,V:1+1+[(?1-1- 1)+1]+[■：>-1-^+1)]+1+1■「n==一p+1所以有：MAX:1+1+[(n-1)+1]+[(n-1)]x3+1+1=•①+1MIN：I+1+[(rt-1)+l]+[(n-1)]+I,+1=2?z+3故「；,：,..「、的运行时间是i-Partition(6x—A[r]i<—p-Afoi-j<—ptor—1doifA[j]2xtheni<i+1exchangeA[i]h-A[j]exchangeA[i+1]A[r]8returni+1快速排序的性能：如果(/.门门了on过程)划分是对称的，那么本算法从渐在意义上讲，不合并排序算法一样快(H(r,)g可)；如果划分是开对称的，那么本算法渐在上就和插入算法一样慢(插入算法最佳0㈤，最差3(次必最坏情况：快速排序的最坏情况发生在划分过程产生的两个区域分别包含 ।个元素和1个0门—1元素(空的)的时候。假设算法每次递归调用中都出现了返种开对称划分。划分的时间代价为®(3。因为对一个大小为0的数组在行递归调用后，远回71⑴=日(1),故算法的运行时间可以递归地表示为：T{u}=T(rt>—1)+'11((])+6(也)=T也—1)+。(记得到T(叫=3附最佳情况：当门了。\过程中两个子问题规模分别为m/鳏口W2]_1时，快速排序运行达到最佳。其运行时间可以递归地表达为：T(n)W2—2)+6(n)解得/因此，快速排序的最佳运行时间是।「；,：，，最差运行时间是小。平衡的划分：快速排序的平均情况运行时间不具最佳情况运行时间很接近，而开是非常接近于其最坏情况运行时间。简单的验证：假设划分过程很开平衡(就是趋向于出现最坏情况，但迓没至撮坏情况)，划分比例为/_1：：1(逆值使得戈吩明显开平衡，比如使"10时划分比例为9：1),因此有T(n)&T(十■灯)+T(%)+6构造一棵递归树，在返棵递归树上，每层的代价是一样的(因为递归过程中了前的系数是1),都是树的最长路径沿着门.T(fc. (k_1/及乐T…T1，最短路径沿着nT(1次)壮TI14产"T--1，因此得到两个路径的长度分别为1%和匕除”。返里先介绍一个结果：[股n=,何，简证：ciIgn<logan<c2ignJg口1gn&r2—WC2Kn

IgQ=>C]&loga2《立因此，上面两个路径的长度都是H(国必因此总代价都是叮xG(l-n)-e(nl-7<io返里，我们整个分析过程都是假设等号成立，因此取得的是上界，故总的运行时间应当是0(〃lgn)o返个分析过程说明，快速排序一般情况下的运行状况都接近于最佳状况。练习7.2-1「做替换后得到，.। ；-..।一,,假设.,「..，则有:cim2+0(m)W忡2£cam2+9(m)假设匿名函数日的=a，则/病+朋&m2£■+胸因此1m、也C-|W—―7^2>—―.7)1+1 Ui.+1取口= =1即可满足。故T(fi)=T(m+1)=7.2-2返个就是快速排序的最坏情况，因此是E一)7.2-3每一步都是分成了0个元素加上霜_］个元素，因此是最坏情况，利用7.2-1的递归式可以得到运行时间为期小)7.2-4Insertion-Sort[A)forj2toknffth.[A]dokctj<A[j[[>hisert才〃]it13thesorted ,4[I..j—I.4—j—।whilez>□andAfi]>keydo.4R+1]-A[^]i^i-1S 1].key根据两种排序算法的性质，对一个具有较好的已排序程度的数组,INSHTIGN-，即接的运行时间是『一.，即接近于「一：「…的最佳的最佳运INSHTIGN-行时间，而*、一：.恰好相反，对一个具有相当排序程度的数组，一门的运行时间更趋向于最坏情况，即…..；，因此在返类问题上插入排序往往比快速排序具有更好的性能。7.2-5递归树是、I -■1 .因此最短和最长两个路径(先开考虑哪个长、哪个短)是at(1「m神->(1-a)2n-> >1和nTcmTh叼.T…T1算得两个路径的长度是一]g笈/lgR,- —G)因为0y1/2，因此口K1一Q，所以—L/lg+<-l/lg(J-a)，故最大深度是-a)1最小深度是—]g呵】g门。快速排序的随机化版本：RANDOMIZID-PArillTIONf^.7AT)i<—RANDOM(p.t)e-.rchange4[r]hA\i\returnPARiITION(A.p.r)Random[Z]j)-QuiCKSoRT(x4.?j,r)if??