分治策略快速排序

分治策略快速排序第一頁，共三十一頁，編輯于2023年，星期五QuickSortSelectapivot(partitioningelement)RearrangethelistsothatalltheelementsinthepositionsbeforethepivotaresmallerthanorequaltothepivotandthoseafterthepivotarelargerthanthepivotExchangethepivotwiththelastelementinthefirst(i.e.,≤sublist)–thepivotisnowinitsfinalpositionSortthetwosublists2第二頁，共三十一頁，編輯于2023年，星期五2.5快速排序問題基本策略是：將數組A[1:n]分解成兩個子數組B[1:p]和B[p+1:n]，使得B[1:p]中的元素均不大于B[p+1:n]中的元素，然后分別對這里兩個數組中的元素進行排序（非降的），最后再把兩個排好序的數組接起來即可。pA[i]≤pA[i]>p3第三頁，共三十一頁，編輯于2023年，星期五選取A的某個元素t=A(s)，然后將其他元素重新排列，使A(1:n)中所有在t以前出現(xiàn)的元素都小于或等于t，而在t之后出現(xiàn)的元素都大于或等于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快速排序問題4第四頁，共三十一頁，編輯于2023年，星期五Thepartitionalgorithm5第五頁，共三十一頁，編輯于2023年，星期五算法步驟分解(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]都已排好的序后步需執(zhí)行任何計算a[p:r]就已排好序。2.5快速排序問題6第六頁，共三十一頁，編輯于2023年，星期五快速排序template<classType>voidQuickSort(Typea[],intp,intr){if(p<r){intq=Partition(a,p,r);QuickSort(a,p,q-1);//對左半段排序

QuickSort(a,q+1,r);//對右半段排序

}}a的起始位置a的終止位置Partition函數負責將a進行一次分割，返回分割元素的位置快速排序問題2.5快速排序問題7第七頁，共三十一頁，編輯于2023年，星期五劃分過程Partition的過程中，首先要選擇一個元素，根據其值劃分數組。稱該元素為中軸。選擇中軸有許多不同的策略，我們使用最簡單的策略，選擇第一個元素：s=a[p]?？焖倥判騿栴}2.5快速排序問題8第八頁，共三十一頁，編輯于2023年，星期五劃分舉例(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)ip657075808560555045+∞29654575808560555070+∞38654550808560557570+∞47654550558560807570+∞56654550556085807570+∞65604550556585807570+∞快速排序問題2.5快速排序問題Figure2-19第九頁，共三十一頁，編輯于2023年，星期五劃分的過程使用一種兩次掃描子數組的方法:一次是從左到右,另一次是從右到左,每次都把子數組的元素和中軸進行比較。從左到右的掃描從第二個元素開始,希望小于中軸的元素位于子數組的第一部分，掃描會忽略小于中軸的元素，直到遇到第一個大于等于中軸的元素才會停止。從右到左的掃描從最后一個元素開始，因為我們希望大于中軸的元素位于子數組的第二部分，掃描會忽略大于中軸的元素，直到遇到第一個小于等于中軸的元素才會停止。快速排序問題2.5快速排序問題10第十頁，共三十一頁，編輯于2023年，星期五P全部<=p>=p·····<=p全部>=pij全部>=p=p全部<=pPi=j全部>=p>=p<=p全部<=pPij快速排序問題如果掃描指針i和j不相交，i<j,簡單交換A[i]和A[j]，再分別對i加1，j減1，然后繼續(xù)掃描如果掃描指針i和j相交，i>j,把中軸和A[j]交換，得到該數組的一個分區(qū)。如果掃描指針i指向同一元素，i＝j，被指向元素的值一定等于p。2.5快速排序問題11第十一頁，共三十一頁，編輯于2023年，星期五劃分程序template<classType>intPartition(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快速排序問題該算法是否有問題？12第十二頁，共三十一頁，編輯于2023年，星期五快速排序問題例：排列5，3，1，9，8，2，4，701234567

ij53198247

ij53198247

ij53148297

ij53148297

ij53142897

ji53142897

2

3145897

ij2

314ij2

314ij2

134ji2

1341

2341ij

34ji

344ij8

97ji8

79789792.5快速排序問題13第十三頁，共三十一頁，編輯于2023年，星期五問題：掃描停止的時候i和j有幾種關系，每種代表哪種情況？下標i和j會不會超出a的下標界？該排序算法是否穩(wěn)定？快速排序問題2.5快速排序問題14第十四頁，共三十一頁，編輯于2023年，星期五EfficiencyofQuickSortBestcase:splitinthemiddle—

Θ(nlogn)Worstcase:sortedarray!—

Θ(n2)Averagecase:randomarrays—

Θ(nlogn)Improvements:betterpivotselection:medianofthreepartitioningavoidsworstcaseinsortedfilesswitchtoinsertionsortonsmallsubfileseliminationofrecursionthesecombineto20-25%improvementConsideredthemethodofchoiceforinternalsortingforlargefiles(n≥10000)15第十五頁，共三十一頁，編輯于2023年，星期五算法分析最壞情況：劃分的兩個區(qū)域分別包含n-1個元素和1個元素，也就是已經排好序的數組。如果用A[0]作為中軸，從左到右的掃描會停在A[1]上，而從右到左的掃描會一直處理到A[0]，導致分裂點出現(xiàn)在0這個位置，所以，在進行了n＋1次比較之后建立了分區(qū)，并且將A[0]和它本身進行了交換以后，快速排序算法還會對嚴格遞增的數組A[1···n-1]進行排序，對規(guī)模減小了的嚴格遞增數組的排序會一直繼續(xù)到最后一個子數組A[n-2···n-1]，這種情況下，鍵值比較的總次數應該等于：(n+1)+n+…+3=O(n2)快速排序問題2.5快速排序問題16第十六頁，共三十一頁，編輯于2023年，星期五算法分析最壞情況：劃分的兩個區(qū)域分別包含n－1個元素和1個元素，如果每一步都出現(xiàn)這種情況，其復雜性T(n)

O(1)n≤1

T(n)=

T(n-1)+O(n)n>1解得：T(n)=O(n2)快速排序問題2.5快速排序問題17第十七頁，共三十一頁，編輯于2023年，星期五最好情況:每次劃分所取的基準都恰好為中值，即每次劃分都產生兩個大小為n/2的區(qū)域，

O(1)n≤1T(n)=2T(n/2)+O(n)n>1T(n)=O(nlogn)快速排序問題2.5快速排序問題18第十八頁，共三十一頁，編輯于2023年，星期五計數排序、冒泡排序、插入排序、選擇排序、歸并排序和快速排序的時間復雜性如下：算法最壞復雜性平均復雜性冒泡排序n2n2計數排序n2n2插入排序n2n2選擇排序n2n2快速排序n2nlogn歸并排序nlognnlogn快速排序問題2.5快速排序問題19第十九頁，共三十一頁，編輯于2023年，星期五2.6線性時間選擇

SelectioninLinearTime問題：已知n元數組A[1:n]，試確定其中第k小的元素。如果k＝1，就是找最小的元素，如果k＝n，就是找最大的元素。2.6線性時間選擇20第二十頁，共三十一頁，編輯于2023年，星期五利用快速分類思想解決這一問題根據PARTITION過程。如果劃分元素v確定在A(j)的位置上，則有j-1個元素小于或等于A(j)，且有n-j個元素大于或等于A(j)。2.6線性時間選擇21第二十一頁，共三十一頁，編輯于2023年，星期五假設在一次劃分中，劃分元素v處于第j個位置。如果k<j，則要找的第k小元素在新數組A[1:j-1]中，而且是A[1:j-1]的第k小元素；如果k＝j，則劃分元素v即是要找的第k小元素；如果k>j，則要找的第k小元素在新數組A[j＋1:n]中,而且是A[j＋1:n]的第k-j小元素。2.6線性時間選擇22第二十二頁，共三十一頁，編輯于2023年，星期五采用劃分的選擇算法

若k=j，則A(j)即是第k小元素；否則，若k<j，則第k小元素為A(1:j-1)中第k小元素；若k>j，則第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劃分元素k<j時，第k小元素所在的集合K>j時，第k小元素所在的集合K=j時，第k小元素就是劃分元素2.6線性時間選擇23第二十三頁，共三十一頁，編輯于2023年，星期五template<classType>TypeRandomizedSelect(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線性時間選擇24第二十四頁，共三十一頁，編輯于2023年，星期五例：4，1，10，9，7，12，8，2，15中尋找第5個最小元素，假設下標從1到9第一次調用Randomizedpartition(a,1,9)=3得到2149712810155>3，調用RandomizedSelect(a,4,9,2)第二次調用Randomizedpartition(a,4,9)=6得到21

4879

1210155<6，調用RandomizedSelect(a,4,6,2)第二次調用Randomizedpartition(a,4,6)=5得到21

478

9

1210152.6線性時間選擇25第二十五頁，共三十一頁，編輯于2023年，星期五算法復雜度：在最壞情況下，總是在最大元素處劃分，算法RandomizedSelect需要O(n2)計算時間。但可以證明，算法RandomizedSelect可以在O(n)平均時間內找出n個輸入元素中的第k小元素。2.6線性時間選擇26第二十六頁，共三十一頁，編輯于2023年，星期五如果能在線性時間內找到一個劃分基準，使得按這個基準所劃分出的2個子數組的長度都至少為原數組長度的ε倍(0<ε<1是某個正常數)，那么就可以在最壞情況下用O(n)時間完成選擇任務。例如，若ε=9/10，算法遞歸調用所產生的子數組的長度至少縮短1/10。所以，在最壞情況下，算法所需的計算時間T(n)滿足遞歸式T(n)≤T(9n/10)+O(n)。由此可得T(n)=O(n)。2.6線性時間選擇27第二十七頁，共三十一頁，編輯于2023年，星期五將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線性時間選擇28第二十八頁，共三十一頁，編輯于2023年，星期五privatestaticComparableselect(intp,intr,intk){

if(r-p<5){//用某個簡單排序算法對數組a[p:r]排序;

b