1、Software College, Northeast University 2.5 快速排序問題快速排序問題l由著名計算機科學家霍爾由著名計算機科學家霍爾(C.A.R.Hoare)給出。給出。l把原序列分成兩個子問題，在被分成的兩個子把原序列分成兩個子問題，在被分成的兩個子問題以后不再需要歸并。問題以后不再需要歸并。l被分成的兩個子問題必須滿足一子問題中的所被分成的兩個子問題必須滿足一子問題中的所有元素都小于或等于另一子問題的任何一個元有元素都小于或等于另一子問題的任何一個元素。素。Software College, Northeast University 2.5 快速排序問題快速排序問題

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

3、或等于小于或等于t，而在，而在t之后出現(xiàn)的元素都大于或之后出現(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)經(jīng)過一次劃分后經(jīng)過一次劃分后每個元素都小于或等于每個元素都小于或等于t每個元素都大于或等于每個元素都大于或等于t快速排序問題快速排序問題Software College, Northeast University 算法步驟算法步驟分解分解(Divide):以以ap為基準元素將為基準元素將ap:r劃分成劃分成3段段ap:q-1,aq和和aq+1:r,使得使得ap:q-1中任何一中任何一個小于等于

4、個小于等于aq,下標下標q在劃分過程中確定。在劃分過程中確定。遞歸求解遞歸求解(conquer):通過遞歸調(diào)用快速排序算法通過遞歸調(diào)用快速排序算法分別對分別對ap:q-1和和aq+1:r進行排序。進行排序。合并合并(Merge):由于對由于對ap:q-1和和aq+1:r的排序是的排序是就地進行的，所以在就地進行的，所以在ap:q-1和和aq+1:r都已排好都已排好的序后步需執(zhí)行任何計算的序后步需執(zhí)行任何計算ap:r就已排好序。就已排好序。快速排序問題快速排序問題Software College, Northeast University 快速排序快速排序Templatevoid QuickSo

5、rt(Type a , int p,int r) if(pr) int q=Partition(a,p,r); QuickSort(a,p,q-1);/對左半段排序?qū)ψ蟀攵闻判?QuickSort(a,q+1,r);/對右半段排序?qū)τ野攵闻判?a的起始位的起始位置置A的終止位置的終止位置Partition函數(shù)負責將函數(shù)負責將a進行一次分割，返進行一次分割，返回分割元素的位置回分割元素的位置快速排序問題快速排序問題Software College, Northeast University 劃分過程劃分過程lPartition的過程中，首先要選擇一個元素，根的過程中，首先要選擇一個元素，根據(jù)其值

6、劃分數(shù)組。稱該元素為中軸。據(jù)其值劃分數(shù)組。稱該元素為中軸。l選擇中軸有許多不同的策略，我們使用最簡單選擇中軸有許多不同的策略，我們使用最簡單的策略，選擇第一個元素：的策略，選擇第一個元素：s = ap。快速排序問題快速排序問題Software College, Northeast University 劃分舉例劃分舉例(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)ip657075808560555045+29654575808560555070+38654550808560557570+47654550558560807570+56654550556085807570+6560

7、4550556585807570+快速排序問題快速排序問題Software College, Northeast University 劃分的過程劃分的過程l使用一種兩次掃描子數(shù)組的方法使用一種兩次掃描子數(shù)組的方法:一次是一次是從左到右從左到右,另另一次是一次是從右到左從右到左,每次都把子數(shù)組的元素和中軸進行每次都把子數(shù)組的元素和中軸進行比較比較l從左到右的掃描從左到右的掃描從第二個元素從第二個元素開始開始,希望小于中軸的希望小于中軸的元素位于子數(shù)組的第一部分，掃描會忽略小于中軸的元素位于子數(shù)組的第一部分，掃描會忽略小于中軸的元素，元素，直到遇到第一個大于等于中軸的元素才會停止直到遇到第一個大

8、于等于中軸的元素才會停止，l從右到左的掃描從從右到左的掃描從最后一個元素最后一個元素開始，因為我們希望開始，因為我們希望大于中軸的元素位于子數(shù)組的第二部分，掃描會忽略大于中軸的元素位于子數(shù)組的第二部分，掃描會忽略大于中軸的元素，大于中軸的元素，直到遇到第一個小于等于中軸的元直到遇到第一個小于等于中軸的元素才會停止。素才會停止。快速排序問題快速排序問題Software College, Northeast University P全部全部=p=pij全部全部=p=p全部全部=p=p=p全部全部=pPij快速排序問題快速排序問題如果掃描指針如果掃描指針i和和j不相交，不相交，ij, 把中軸和把中軸

9、和Aj交換，得到該數(shù)組的一個分區(qū)。交換，得到該數(shù)組的一個分區(qū)。如果掃描指針如果掃描指針i指向同一元素，指向同一元素，ij，被指向元素的值一定等于，被指向元素的值一定等于p。Software College, Northeast University 劃分程序劃分程序 templateint 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;快速排序問題快速

10、排序問題pr+1a p i = ja j x左側(cè)掃描指針起左側(cè)掃描指針起始始右側(cè)掃描指針起右側(cè)掃描指針起始始中軸元素中軸元素移動左側(cè)掃描指移動左側(cè)掃描指針針移動右側(cè)掃描指針移動右側(cè)掃描指針Software College, Northeast University 快速排序問題快速排序問題例：排列例：排列 5，3，1，9，8，2，4，70 1 2 3 4 5 6 7 i j5 3 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

11、 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 979Software College, Northeast University 問題：問題：l掃描停止的時候掃描停止的時候i和和j有幾種關(guān)系，每種代表哪有幾種關(guān)系，每種代表哪種情況？種情況？l下標下標i和和j會不會超出會不會超出a的下標界？的下標界？l該排序算法是否穩(wěn)定？該排序算法是否穩(wěn)定？快速排序問題快速排序問題Software College, Northeast Univer

12、sity 算法分析l最壞情況：劃分的兩個區(qū)域分別包含最壞情況：劃分的兩個區(qū)域分別包含n1個元素和個元素和1個個元素，也就是已經(jīng)排好序的數(shù)組。如果用元素，也就是已經(jīng)排好序的數(shù)組。如果用A0作為中軸，作為中軸，從左到右的掃描會停在從左到右的掃描會停在A1上，而從右到左的掃描會一上，而從右到左的掃描會一直處理到直處理到A0，導致分裂點出現(xiàn)在，導致分裂點出現(xiàn)在0這個位置，所以，這個位置，所以，在進行了在進行了n1次比較之后建立了分區(qū)，并且將次比較之后建立了分區(qū)，并且將A0 和它和它本身進行了交換以后，快速排序算法還會對嚴格遞增的本身進行了交換以后，快速排序算法還會對嚴格遞增的數(shù)組數(shù)組A1n-1進行排序

13、，對規(guī)模減小了的嚴格遞增數(shù)進行排序，對規(guī)模減小了的嚴格遞增數(shù)組的排序會一直繼續(xù)到最后一個子數(shù)組組的排序會一直繼續(xù)到最后一個子數(shù)組An-2n-1，這，這種情況下，鍵值比較的總次數(shù)應(yīng)該等于：種情況下，鍵值比較的總次數(shù)應(yīng)該等于：l(n+1)+n+3=O(n2)快速排序問題快速排序問題Software College, Northeast University 算法分析l最壞情況：劃分的兩個區(qū)域分別包含最壞情況：劃分的兩個區(qū)域分別包含n1個元個元素和素和1個元素，如果每一步都出現(xiàn)這種情況，個元素，如果每一步都出現(xiàn)這種情況，其復雜性其復雜性T(n) O(1) n1 T(n)= T(n-1)+O(n) n

14、1解得：解得：T(n)=O(n2)快速排序問題快速排序問題Software College, Northeast University l最好情況最好情況l每次劃分所取的基準都恰好為中值，即每次劃每次劃分所取的基準都恰好為中值，即每次劃分都產(chǎn)生兩個大小為分都產(chǎn)生兩個大小為n/2的區(qū)域，的區(qū)域， O(1) n1 T(n)= 2T(n/2)+O(n) n1T(n)=O(nlogn)快速排序問題快速排序問題Software College, Northeast University 計數(shù)排序、冒泡排序、插入排序、選擇排序、歸并排序和快速排序的時間復雜性如下：l算法算法 最壞復雜性最壞復雜性 平均復雜

15、性平均復雜性l冒泡排序冒泡排序 n2 n2l計數(shù)排序計數(shù)排序 n2 n2l插入排序插入排序 n2 n2l選擇排序選擇排序 n2 n2l快速排序快速排序 n2 n log nl歸并排序歸并排序 n log n n log n 快速排序問題快速排序問題Software College, Northeast University 2.6 線性時間選擇線性時間選擇問題：問題：已知已知n元數(shù)組元數(shù)組A1:n，試確定其中第，試確定其中第k小小的元素。的元素。如果如果k1，就是找最小的元素，如果，就是找最小的元素，如果kn，就是找最大的元素。就是找最大的元素。Software College, Northe

16、ast University 利用快速分類思想解決這一問題利用快速分類思想解決這一問題根據(jù)根據(jù)PARTITION過程。如果劃分元素過程。如果劃分元素v確定在確定在A(j)的位置上，則有的位置上，則有j-1個元素小于或等于個元素小于或等于A(j)，且有且有n-j個元素大于或等于個元素大于或等于A(j)。假設(shè)在一次劃分中，劃分元素假設(shè)在一次劃分中，劃分元素v處于第處于第j個位置。個位置。如果如果kj，則要找的第則要找的第k小元素在新數(shù)組小元素在新數(shù)組Aj1:n中中,而且而且是是Aj1:n的第的第k-j小元素小元素Software College, Northeast University 采用劃分

17、的選擇算法采用劃分的選擇算法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小元小元素就是劃分元素素就是劃分元素Software College, Northeast University templateType RandomizedSelect(Type a ,int p,int r,int k) if(p = r) return a

18、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)用第二次調(diào)用Randomizedpartition(a, 4, 6)=5得到得到 2 1 4 7 8 9 12 10 15Software College, Northeast University 算法復雜度l與快排的區(qū)別：只處理一個子數(shù)組與快排的區(qū)別：只處理一個子數(shù)組l最壞情況：總是在最大元素處劃分，算法需要最壞情況：總是在最大元素處劃分，算法需要 l平均情況：設(shè)平均比較次數(shù)為平均情況：設(shè)平均比較次數(shù)為C(n)，則兩個子集分別為，則兩個子集分別為k-1, n-k，兩個子集的元素平均比較次數(shù)分別為，兩個子集的元素平均比較次數(shù)分別為C(k-1)和和C(n-k) ，由此得到遞歸關(guān)系式：由此得到遞歸關(guān)系式：lnC( n