1、12.5 快速排序問題快速排序問題 QuickSortl由著名計算機科學(xué)家霍爾由著名計算機科學(xué)家霍爾(C.A.R.Hoare)給出。給出。l把原序列分成兩個子問題，在被分成的兩個子把原序列分成兩個子問題，在被分成的兩個子問題以后不再需要歸并。問題以后不再需要歸并。l被分成的兩個子問題必須滿足一子問題中的所被分成的兩個子問題必須滿足一子問題中的所有元素都小于或等于另一子問題的任何一個元有元素都小于或等于另一子問題的任何一個元素。素。2QuickSortlSelect a pivot (partitioning element)lRearrange the list so that all the

2、 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 lExchange the pivot with the last element in the first (i.e., sublist) the pivot is now in its final positionlSort the two sublists32.5 快速排序問題快速排序問題基本策略是：基本策略是：將數(shù)組將數(shù)

3、組A1:n分解成兩個子數(shù)組分解成兩個子數(shù)組B1:p和和Bp+1:n，使得，使得B1:p中的元素均不大于中的元素均不大于Bp+1:n中的元素，然后分別對這里兩個中的元素，然后分別對這里兩個數(shù)組中的元素進行排序（非降的），最后數(shù)組中的元素進行排序（非降的），最后再把兩個排好序的數(shù)組接起來即可。再把兩個排好序的數(shù)組接起來即可。pAipAip4l選取選取A的某個元素的某個元素t=A(s)，然后將其他元素重，然后將其他元素重新排列，使新排列，使A(1:n)中所有在中所有在t以前出現(xiàn)的元素都以前出現(xiàn)的元素都小于或等于小于或等于t，而在，而在t之后出現(xiàn)的元素都大于或之后出現(xiàn)的元素都大于或等于等于t。A(1)

4、A(2)A(s-1)A(s)A(s+1)A(n)t劃分元素劃分元素A(n)A(k)tA(j)A(2)A(1)經(jīng)過一次劃分后經(jīng)過一次劃分后每個元素都小于或等于每個元素都小于或等于t每個元素都大于或等于每個元素都大于或等于t2.5 快速排序問題快速排序問題5The partition algorithm6算法步驟算法步驟l分解分解(Divide):以以ap為基準元素將為基準元素將ap:r劃分成劃分成3段段ap:q-1,aq和和aq+1:r,使得使得ap:q-1中任何一中任何一個小于等于個小于等于aq,下標下標q在劃分過程中確定。在劃分過程中確定。l遞歸求解遞歸求解(conquer):通過遞歸調(diào)用快

5、速排序算法通過遞歸調(diào)用快速排序算法分別對分別對ap:q-1和和aq+1:r進行排序。進行排序。l合并合并(Merge):由于對由于對ap:q-1和和aq+1:r的排序是的排序是就地進行的，所以在就地進行的，所以在ap:q-1和和aq+1:r都已排好都已排好的序后步需執(zhí)行任何計算的序后步需執(zhí)行任何計算ap:r就已排好序。就已排好序。2.5快速排序問題快速排序問題7快速排序快速排序templatevoid QuickSort(Type a , int p,int r) if(pr) int q=Partition(a,p,r); QuickSort(a,p,q-1);/對左半段排序?qū)ψ蟀攵闻判?Q

6、uickSort(a,q+1,r);/對右半段排序?qū)τ野攵闻判?a的起始位的起始位置置a的終止位置的終止位置Partition函數(shù)負責將函數(shù)負責將a進行一次分割，返進行一次分割，返回分割元素的位置回分割元素的位置快速排序問題快速排序問題2.5快速排序問題快速排序問題8劃分過程劃分過程lPartition的過程中，首先要選擇一個元素，根的過程中，首先要選擇一個元素，根據(jù)其值劃分數(shù)組。稱該元素為中軸。據(jù)其值劃分數(shù)組。稱該元素為中軸。l選擇中軸有許多不同的策略，我們使用最簡單選擇中軸有許多不同的策略，我們使用最簡單的策略，選擇第一個元素：的策略，選擇第一個元素：s = ap?？焖倥判騿栴}快速排序問題

7、2.5快速排序問題快速排序問題9劃分舉例劃分舉例(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)ip657075808560555045+29654575808560555070+38654550808560557570+47654550558560807570+56654550556085807570+65604550556585807570+快速排序問題快速排序問題2.5快速排序問題快速排序問題 Figure 2-110劃分的過程劃分的過程l使用一種兩次掃描子數(shù)組的方法使用一種兩次掃描子數(shù)組的方法:一次是一次是從左到右從左到右,另另一次是一次是從右到左從右到左,每次都把子數(shù)組

8、的元素和中軸進行每次都把子數(shù)組的元素和中軸進行比較。比較。l從左到右的掃描從左到右的掃描從第二個元素從第二個元素開始開始,希望小于中軸的希望小于中軸的元素位于子數(shù)組的第一部分，掃描會忽略小于中軸的元素位于子數(shù)組的第一部分，掃描會忽略小于中軸的元素，元素，直到遇到第一個大于等于中軸的元素才會停止直到遇到第一個大于等于中軸的元素才會停止。l從右到左的掃描從從右到左的掃描從最后一個元素最后一個元素開始，因為我們希望開始，因為我們希望大于中軸的元素位于子數(shù)組的第二部分，掃描會忽略大于中軸的元素位于子數(shù)組的第二部分，掃描會忽略大于中軸的元素，大于中軸的元素，直到遇到第一個小于等于中軸的元直到遇到第一個小

9、于等于中軸的元素才會停止。素才會停止?？焖倥判騿栴}快速排序問題2.5快速排序問題快速排序問題11P全部全部=p=pij全部全部=p=p全部全部=p=p=p全部全部=pPij快速排序問題快速排序問題如果掃描指針如果掃描指針i和和j不相交，不相交，ij, 把中軸和把中軸和Aj交換，得到該數(shù)組的一個分區(qū)。交換，得到該數(shù)組的一個分區(qū)。如果掃描指針如果掃描指針i指向同一元素，指向同一元素，ij，被指向元素的值一定等于，被指向元素的值一定等于p。2.5快速排序問題快速排序問題12劃分程序劃分程序 template int Partition(Type a ,int p,int r) int i = , j

10、 = ; Type x = ; while( true ) while( a +i x ); if( ) break; Swap( a i , a j ); a p = ; a j = ; return j;快速排序問題快速排序問題pr+1a p i = ja j x左側(cè)掃描指針起左側(cè)掃描指針起始始右側(cè)掃描指針起始右側(cè)掃描指針起始中軸元素中軸元素移動左側(cè)掃描指移動左側(cè)掃描指針針移動右側(cè)掃描指針移動右側(cè)掃描指針2.5快速排序問題快速排序問題該算法是否有問題？該算法是否有問題？13快速排序問題快速排序問題例：排列例：排列 5，3，1，9，8，2，4，70 1 2 3 4 5 6 7 i j5 3

11、1 9 8 2 4 7 i j5 3 1 9 8 2 4 7 i j5 3 1 4 8 2 9 7 i j5 3 1 4 8 2 9 7 i j5 3 1 4 2 8 9 7 j i5 3 1 4 2 8 9 7 2 3 1 4 5 8 9 7 i j2 3 1 4 i j2 3 1 4 i j2 1 3 4 j i2 1 3 41 2 3 41 i j 3 4 j i 3 4 4 i j8 9 7 j i8 7 97 8 9792.5快速排序問題快速排序問題14問題：問題：l掃描停止的時候掃描停止的時候i和和j有幾種關(guān)系，每種代表哪有幾種關(guān)系，每種代表哪種情況？種情況？l下標下標i和和j會不

12、會超出會不會超出a的下標界？的下標界？l該排序算法是否穩(wěn)定？該排序算法是否穩(wěn)定？快速排序問題快速排序問題2.5快速排序問題快速排序問題15Efficiency of QuickSortlBest case: split in the middle ( n log n) lWorst case: sorted array! ( n2) lAverage case: random arrays ( n log n)lImprovements:lbetter pivot selection: median of three partitioning avoids worst case in sort

13、ed fileslswitch to insertion sort on small subfileslelimination of recursionthese combine to 20-25% improvementlConsidered the method of choice for internal sorting for large files (n 10000)16算法分析l最壞情況：劃分的兩個區(qū)域分別包含最壞情況：劃分的兩個區(qū)域分別包含n-1個元素和個元素和1個元個元素，也就是已經(jīng)排好序的數(shù)組。如果用素，也就是已經(jīng)排好序的數(shù)組。如果用A0作為中軸，作為中軸，從左到右的掃描會停

14、在從左到右的掃描會停在A1上，而從右到左的掃描會一上，而從右到左的掃描會一直處理到直處理到A0，導(dǎo)致分裂點出現(xiàn)在，導(dǎo)致分裂點出現(xiàn)在0這個位置，所以，這個位置，所以，在進行了在進行了n1次比較之后建立了分區(qū)，并且將次比較之后建立了分區(qū)，并且將A0 和它和它本身進行了交換以后，快速排序算法還會對嚴格遞增的本身進行了交換以后，快速排序算法還會對嚴格遞增的數(shù)組數(shù)組A1n-1進行排序，對規(guī)模減小了的嚴格遞增數(shù)進行排序，對規(guī)模減小了的嚴格遞增數(shù)組的排序會一直繼續(xù)到最后一個子數(shù)組組的排序會一直繼續(xù)到最后一個子數(shù)組An-2n-1，這，這種情況下，鍵值比較的總次數(shù)應(yīng)該等于：種情況下，鍵值比較的總次數(shù)應(yīng)該等于：l

15、(n+1)+n+3=O(n2)快速排序問題快速排序問題2.5快速排序問題快速排序問題17算法分析l最壞情況：劃分的兩個區(qū)域分別包含最壞情況：劃分的兩個區(qū)域分別包含n1個元個元素和素和1個元素，如果每一步都出現(xiàn)這種情況，個元素，如果每一步都出現(xiàn)這種情況，其復(fù)雜性其復(fù)雜性T(n) O(1) n1 T(n)= T(n-1)+O(n) n1解得：解得：T(n)=O(n2)快速排序問題快速排序問題2.5快速排序問題快速排序問題18l最好情況最好情況:每次劃分所取的基準都恰好為中值，每次劃分所取的基準都恰好為中值，即每次劃分都產(chǎn)生兩個大小為即每次劃分都產(chǎn)生兩個大小為n/2的區(qū)域，的區(qū)域， O(1) n1

16、T(n)= 2T(n/2)+O(n) n1 T(n)=O(nlogn)快速排序問題快速排序問題2.5快速排序問題快速排序問題19計數(shù)排序、冒泡排序、插入排序、選擇排序、歸并排序和快速排序的時間復(fù)雜性如下：l算法算法 最壞復(fù)雜性最壞復(fù)雜性 平均復(fù)雜性平均復(fù)雜性l冒泡排序冒泡排序 n2 n2l計數(shù)排序計數(shù)排序 n2 n2l插入排序插入排序 n2 n2l選擇排序選擇排序 n2 n2l快速排序快速排序 n2 n log nl歸并排序歸并排序 n log n n log n 快速排序問題快速排序問題2.5快速排序問題快速排序問題202.6 線性時間選擇線性時間選擇 Selection in Linear

17、 Time l問題：問題：已知已知n元數(shù)組元數(shù)組A1:n，試確定其中第，試確定其中第k小小的元素。的元素。l如果如果k1，就是找最小的元素，如果，就是找最小的元素，如果kn，就是找最大的元素。就是找最大的元素。2.6 線性時間選擇線性時間選擇21l利用快速分類思想解決這一問題利用快速分類思想解決這一問題l根據(jù)根據(jù)PARTITION過程。如果劃分元素過程。如果劃分元素v確定在確定在A(j)的位置上，則有的位置上，則有j-1個元素小于或等于個元素小于或等于A(j)，且有且有n-j個元素大于或等于個元素大于或等于A(j)。2.6 線性時間選擇線性時間選擇22l假設(shè)在一次劃分中，劃分元素假設(shè)在一次劃分

18、中，劃分元素v處于第處于第j個位置。個位置。如果如果kj，則要找的第，則要找的第k小元素在新數(shù)組小元素在新數(shù)組Aj1:n中中,而且是而且是Aj1:n的第的第k-j小元素。小元素。2.6 線性時間選擇線性時間選擇23采用劃分的選擇算法采用劃分的選擇算法l 若若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

19、線性時間選擇線性時間選擇24templateType 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，調(diào)用，調(diào)用RandomizedSelect( a, 4, 9, 2)第二次調(diào)用第二次調(diào)用Randomizedpartition(a, 4, 9)=6得到得到 2 1 4 8 7 9 12 10 1556，調(diào)用，調(diào)用RandomizedSelect( a, 4, 6, 2)第二次調(diào)用第二

20、次調(diào)用Randomizedpartition(a, 4, 6)=5得到得到 2 1 4 7 8 9 12 10 152.6 線性時間選擇線性時間選擇26算法復(fù)雜度：l在最壞情況下，總是在最大元素處劃分，算法RandomizedSelect需要O(n2)計算時間。l但可以證明，算法RandomizedSelect可以在O(n)平均時間內(nèi)找出n個輸入元素中的第k小元素。2.6 線性時間選擇線性時間選擇27如果能在線性時間內(nèi)找到一個劃分基準，使得按這個基準所劃分出的2個子數(shù)組的長度都至少為原數(shù)組長度的倍(01是某個正常數(shù))，那么就可以在最壞情況下在最壞情況下用O(n)時間完成選擇任務(wù)。例如，若=9/

21、10，算法遞歸調(diào)用所產(chǎn)生的子數(shù)組的長度至少縮短1/10。所以，在最壞情況下，算法所需的計算時間T(n)滿足遞歸式T(n)T(9n/10)+O(n) 。由此可得T(n)=O(n)。2.6 線性時間選擇線性時間選擇28l將n個輸入元素劃分成n/5個組，每組5個元素，只可能有一個組不是5個元素。用任意一種排序算法，將每組中的元素排好序，并取出每組的中位數(shù)，共n/5個。l遞歸調(diào)用selectselect來找出這n/5個元素的中位數(shù)。如果n/5是偶數(shù)，就找它的2個中位數(shù)中較大的一個。以這個元素作為劃分基準。設(shè)所有元素互不相同。在這種情況下，找出的基準x至少比3(n-5)/10個元素大，因為在每一組中有2

22、個元素小于本組的中位數(shù)，而n/5個中位數(shù)中又有(n-5)/10個小于基準x。同理，基準x也至少比3(n-5)/10個元素小。而當n75時，3(n-5)/10n/4所以按此基準劃分所得的2個子數(shù)組的長度都至少縮短1/4。2.6 線性時間選擇線性時間選擇29private static Comparable select (int p, int r, int k) if (r-p5) /用某個簡單排序算法對數(shù)組ap:r排序; bubbleSort(p,r); return ap+k-1; /將ap+5*i至ap+5*i+4的第3小元素 /與ap+i交換位置; /找中位數(shù)的中位數(shù)，r-p-4即上面所

23、說的n-5 for ( int i = 0; i=(r-p-4)/5; i+ ) int s=p+5*i, t=s+4; for (int j=0;j3;j+) bubble(s,t-j); MyMath.swap(a, p+i, s+2); Comparable x = select(p, p+(r-p-4)/5, (r-p-4)/10); int i=partition(p,r,x), j=i-p+1; if (k=j) return select(p,i,k); else return select(i+1,r,k-j); 復(fù)雜度分析復(fù)雜度分析T(n)=O(n)7575)4/3()5/(

24、)(21nnnTnTnCCnT上述算法將每一組的大小定為5，并選取75作為是否作遞歸調(diào)用的分界點。這2點保證了T(n)的遞歸式中2個自變量之和n/5+3n/4=19n/20=n，01。這是使T(n)=O(n)的關(guān)鍵之處。當然，除了5和75之外，還有其他選擇。2.6 線性時間選擇線性時間選擇30l自學(xué) 改進的線性時間選擇l作業(yè) 教材P37頁，2-1531ExerciseslUsing Figure 2-1 as a model, illustrate the operation of PARTITION on the array A = 13, 19, 9, 5, 12, 8, 7, 4, 11, 2, 6, 21. 32ExerciseslGive a brief argument that the running time of PARTITION on a subarray of size n is (n). lHow would yo