排序算法之－－快速排序

快速排序 

分而治之方法還可以用于實作另一種完全不同的排序方法，這種排序法稱為快速排序（quick sort）。在這種方法中， n 個元素被分成三段（組）：左段l e f t，右段r i g h t和中段m i d d l e。中段僅包含一個元素。左段中各元素都小于等于中段元素，右段中各元素都大于等于中段元素。是以l e f t和r i g h t中的元素可以獨立排序，并且不必對l e f t和r i g h t的排序結果進行合并。m i d d l e中的元素被稱為支點( p i v o t )。圖1 4 - 9中給出了快速排序的僞代碼。 

/ /使用快速排序方法對a[ 0 :n- 1 ]排序 

從a[ 0 :n- 1 ]中選擇一個元素作為m i d d l e，該元素為支點 

把餘下的元素分割為兩段left 和r i g h t，使得l e f t中的元素都小于等于支點，而right 中的元素都大于等于支點 

遞歸地使用快速排序方法對left 進行排序 

遞歸地使用快速排序方法對right 進行排序 

所得結果為l e f t + m i d d l e + r i g h t 

圖14-9 快速排序的僞代碼 

考察元素序列[ 4 , 8 , 3 , 7 , 1 , 5 , 6 , 2 ]。假設選擇元素6作為支點，則6位于m i d d l e；4，3，1，5，2位于l e f t；8，7位于r i g h t。當left 排好序後，所得結果為1，2，3，4，5；當r i g h t排好序後，所得結果為7，8。把right 中的元素放在支點元素之後， l e f t中的元素放在支點元素之前，即可得到最終的結果[ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ]。 

把元素序列劃分為l e f t、m i d d l e和r i g h t可以就地進行（見程式1 4 - 6）。在程式1 4 - 6中，支點總是取位置1中的元素。也可以采用其他選擇方式來提高排序性能，本章稍後部分将給出這樣一種選擇。 

程式14-6 快速排序 

template 

void QuickSort(T*a, int n) 

{// 對a[0:n-1] 進行快速排序 

{// 要求a[n] 必需有最大關鍵值 

quickSort(a, 0, n-1); 

template 

void quickSort(T a[], int l, int r) 

{// 排序a [ l : r ]， a[r+1] 有大值 

if (l >= r) return; 

int i = l, // 從左至右的遊标 

j = r + 1; // 從右到左的遊标 

T pivot = a[l]; 

// 把左側>= pivot的元素與右側<= pivot 的元素進行交換 

while (true) { 

do {// 在左側尋找>= pivot 的元素 

i = i + 1; 

} while (a[i] < pivot); 

do {// 在右側尋找<= pivot 的元素 

j = j - 1; 

} while (a[j] > pivot); 

if (i >= j) break; // 未發現交換對象 

Swap(a[i], a[j]); 

} 

// 設定p i v o t 

a[l] = a[j]; 

a[j] = pivot; 

quickSort(a, l, j-1); // 對左段排序 

quickSort(a, j+1, r); // 對右段排序 

} 

若把程式1 4 - 6中d o - w h i l e條件内的<号和>号分别修改為< =和> =，程式1 4 - 6仍然正确。實驗結果表明使用程式1 4 - 6的快速排序代碼可以得到比較好的平均性能。為了消除程式中的遞歸，必須引入堆棧。不過，消除最後一個遞歸調用不須使用堆棧。消除遞歸調用的工作留作練習（練習1 3）。程式1 4 - 6所需要的遞歸棧空間為O (n)。若使用堆棧來模拟遞歸，則可以把這個空間減少為O ( l o gn)。在模拟過程中，首先對left 和right 中較小者進行排序，把較大者的邊界放入堆棧中。在最壞情況下l e f t總是為空，快速排序所需的計算時間為(n2 )。在最好情況下， l e f t和r i g h t中的元素數目大

緻相同，快速排序的複雜性為(nl o gn)。令人吃驚的是，快速排序的平均複雜性也是(nl o gn)。 

定理2-1 快速排序的平均複雜性為(nl o gn)。 

證明用t (n) 代表對含有n 個元素的數組進行排序的平均時間。當n≤1時，t (n)≤d，d為某一常數。當n <1時，用s 表示左段所含元素的個數。由于在中段中有一個支點元素，是以右段中元素的個數為n-s- 1。是以左段和右段的平均排序時間分别為t (s), t (n-s- 1 )。分割數組中元素所需要的時間用cn 表示，其中c 是一個常數。因為s 有同等機會取0 ~n- 1中的任何一個值. 

如對（2 - 8）式中的n 使用歸納法，可得到t (n)≤kn l o ge n，其中n> 1且k=2(c+d)，e～2 . 7 1 8為自然對數的基底。在歸納開始時首先驗證n= 2時公式的正确性。根據公式（ 1 4 - 8），可以得到t( 2 )≤2c+ 2d≤k nl o ge 2。在歸納假設部分，假定t(n)≤kn l o ge n（當2≤n＜m 時，m 是任意一個比2大的整數＝. 

圖1 4 - 1 0對本書中所讨論的算法在平均條件下和最壞條件下的複雜性進行了比較。 

方法最壞複雜性平均複雜性 

冒泡排序n2 n2 

計數排序n2 n2 

插入排序n2 n2 

選擇排序n2 n2 

堆排序nl o gn nl o gn 

歸并排序nl o gn nl o gn 

快速排序n2 nl o gn 

圖14-10 各種排序算法的比較 

中值快速排序（ median-of-three quick sort）是程式1 4 - 6的一種變化，這種算法有更好的平均性能。注意到在程式1 4 - 6中總是選擇a [ 1 ]做為支點，而在這種快速排序算法中，可以不必使用a [ 1 ]做為支點，而是取{a[1],a[(1+r)/2],a[r]} 中大小居中的那個元素作為支點。例如，假如有三個元素，大小分别為5，9，7，那麼取7為支點。為了實作中值快速排序算法，一種最簡單的方式就是首先選出中值元素并與a[1] 進行交換，然後利用程式1 4 - 6完成排序。如果a [ r ]是被選出的中值元素，那麼将a[1] 與a[r] 進行交換，然後将a [ 1 ]（即原來的a [ r ]）指派給程式1 4 - 6中的變量p i v o t，之後繼續執行程式1 4 - 6中的其餘代碼。 

圖2 - 11中分别給出了根據實驗所得到的歸并排序、堆排序、插入排序、快速排序的平均時間。對于每一個不同的n, 都随機産生了至少1 0 0組整數。随機整數的産生是通過反複調用s t d&nbsp;l i b . h庫中的r a n d o m函數來實作的。如果對一組整數進行排序的時間少于1 0個時鐘滴答，則繼續對其他組整數進行排序，直到所用的時間不低于1 0個時鐘滴答。在圖2 - 11中的資料包含産生随機整數的時間。對于每一個n，在各種排序法中用于産生随機整數及其他開銷的時間是相同的。是以，圖2 - 11中的資料對于比較各種排序算法是很有用的。 

對于足夠大的n，快速排序算法要比其他算法效率更高。從圖中可以看到快速排序曲線與插入排序曲線的交點橫坐标比2 0略小，可通過實驗來确定這個交點橫坐标的精确值。可以分别用n = 1 5 , 1 6 , 1 7 , 1 8 , 1 9進行實驗，以尋找精确的交點。令精确的交點橫坐标為nBr e a k。當n≤nBreak 時，插入排序的平均性能最佳。當n＞nBreak 時，快速排序性能最佳。當n＞nBreak 時，把插入排序與快速排序組合為一個排序函數，可以提高快速排序的性能，實作方法是把程式1 4 - 6中的以下語句： 

if(l >= r)r e t u r n ; 

替換為 

if (r-1  

這裡I n s e r t i o n S o r t ( a , l , r )用來對a [ 1 : r ]進行插入排序。測量修改後的快速排序算法的性能留作練習（練習2 0）。用更小的值替換n B r e a k有可能使性能進一步提高（見練習2 0）。 

大多數實驗表明，當n＞c時（c為某一常數），在最壞情況下歸并排序的性能也是最佳的。而當n≤c時，在最壞情況下插入排序的性能最佳。通過将插入排序與歸并排序混合使用，可以提高歸并排序的性能（練習2 1

http://met.fzu.edu.cn/eduonline/web/web/book/6.2.files/frame.htm 這裡更詳細