注：本文如涉及到代碼，均經過Python 3.7實際運行檢驗，保證其嚴謹性。
本文閱讀時間約為6分鐘。
這一節介紹的是最後一種排序算法：快速排序。
快速排序Quick Sort
快速排序的思路，是依據一個“中值”(pivot value)數據項把數據表分為兩半：小於中值的一半和大於中值的一半，然後用遞歸將這兩半分別進行快速排序。
由於找“中值”數據項需要額外的計算開銷，如果出於時間複雜度的考慮，想要省掉這種計算開銷成本，只能隨便找一個數據項充當“中值”，比如第1個數。
快速排序的遞歸三要素如下：
- 基本結束條件——數據表僅有1個數據項，自然是排好序的，結束。
- 縮小規模——根據“中值”，將數據表分為兩半，最好情況是相等規模的兩半。
- 調用自身——將兩半分別調用自身進行排序（排序基本操作在分裂過程中）。
分裂數據表的目標：找到“中值”的位置。
排序是按從左到右的順序從小到大，假定列表中存在一個“中值”，若是中值左邊的數比中值大，或者中值右邊的數比中值小，都屬於“逆序”，反之才是“順序”。
“順序”和“逆序”是我們下面對數的位置是否需要進行交換的判斷依據。
分裂數據表的手段：設置左右標(leftmark/rightmark)，左標向右移動，右表向左移動。左標一直向右移動，碰到比中值大的數據項（即逆序了）就停止；右標一直向左移動，碰到比中值小的數據項（即逆序了）就停止。然後把左右標所指的數據項交換。
繼續移動，直到左標移到右標的右側，停止移動。
這時右標所指位置就是中值應處的位置。將中值的位置和這個位置交換，分裂即完成。
分裂完成的結果是，以中值為界，左半部全部的數據項都比中值小，右半部全部的數據項都比中值大。
快速排序算法的一個實例
下面看看排序算法的一個實例。
問題是，用快速排序對列表[54, 26, 93, 17, 77, 31, 44, 55, 20]進行排序。
Pic-507-1 快速排序算法的一個實例
快速排序的過程如上圖所示：
我們假定列表的第一個數54為“中值”。左標leftmark就是54的下一個數26的位置，而右標rightmark就是最後一個數20所在的位置。
左標要向右移動，右標要向左移動。
左標對應的數26比中值54小（是順序的），於是左標往右移動，碰到第一個數93，而93比中值54要大（逆序了），於是左標停下來。
右標對應的數20比中值54大（是順序的），於是右標往左移動，碰到第一個數55，而55也比中值54要大（逆序了），於是右標也停下來。
這時93和20兩個數互相交換位置（中值為界，比其小的應該在左標這裡，比其大的應該在右標這裡），即把93交換到右標所在位置，把20交換到左標所在位置。
交換位置完畢，左標繼續往右移動，遇到了17，比中值54小（是順序的），繼續往右移動，遇到了77，比中值54大（逆序了），此時左標再度停下來。
右標在交換位置完畢後，也繼續向左移動，遇到了55，比中值大（是順序的），繼續往左移動，遇到了44，比中值54小（逆序了），此時右標也再度停下來了。
此時77和44兩個數也互相交換位置。
交換位置完畢後，左標繼續往右移動，遇到31，比中值54小（是順序的），繼續往右移動，遇到了77，而77此刻處於右標的右邊，也就是左標此時已經越過了右標，停止條件達成。此時，右標所指的31就是中值需要交換的位置。而我們此前假定的中值54，就需要和31這個數互相交換位置。
這樣一來，我們最初假定的中值54，把整個列表分成了兩半，比54小的有5個數，比54大的數有3個數。54就一個數，自然不需要排序。我們利用遞歸對左半部進行快速排序，對右半部進行快速排序。最後達成整個列表排序的目的。這就是整個列表快速排序的過程。
根據以上思路，快速排序算法的具體代碼及相關注釋如下：
<code># 快速排序。
def quickSort(alist):
quickSortHelper(alist, 0, len(alist)-1)
def quickSortHelper(alist, first, last):
if first < last: # 基本結束條件。
splitpoint = partition(alist, first, last) # 分裂，縮小規模。
# 遞歸調用：
quickSortHelper(alist, first, splitpoint-1)
quickSortHelper(alist, splitpoint+1, last)
def partition(alist, first, last):
pivotvalue = alist[first] # 假定中值為第一個數。
leftmark = first + 1 # 左標leftmark的初始值。
rightmark = last # 右標rightmark的初始值。
done = False
while not done:
# 左標leftmark向右移動的過程。
while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
leftmark += 1 # 左標leftmark向右移動。
# 右標rightmark向左移動的過程。
while alist[rightmark] >= pivotvalue and rightmark >= leftmark:
rightmark -= 1 # 右標rightmark向左移動。
if rightmark < leftmark: # 左標到了右標的右邊時，移動終止。
done = True
else:
alist[leftmark], alist[rightmark] = alist[rightmark], alist[leftmark] # 座標對應的值和右標對應的值交換位置。
alist[first], alist[rightmark] = alist[rightmark], alist[first] # 假定的中值和最後得出的中值互換位置。
return rightmark # 返回中值所在的位置，也就是分裂點。
l = [54, 26, 93, 17, 77, 31, 44, 55, 20]
quickSort(l)
print(l)
<
快速排序的算法分析
快速排序的過程分為兩大部分：分裂和移動。
- 如果分裂總能把數據表分為相等的兩部分，那麼快速排序的算法複雜度是O(log n)。
- 而移動需要將每項與中值進行比對，其算法複雜度為O(n)。
綜合看來，快速排序的算法複雜度就是O(nlog n)。而且，快速排序在運行過程中不需要額外的存儲空間。
這樣看來，快速排序的算法性能是非常有優勢的。
但是，快速排序的性能跟中值的選取有很大關係。
存在一些極端情況，比如中值所在的分裂點偏離中間過遠，就會造成左右兩部分數量不平衡。極端情況，有一部分始終沒有數據。
這樣的話，快速排序的時間複雜度就會退化到O(n^2)O(n2)，再加上遞歸調用的開銷，其性能比冒泡排序更糟糕。如果是這種情況，那我們還不如選擇冒泡排序算法。
既然快速排序的算法性能和中值的選取有很大關係，那麼我們是否可以通過改進中值的選取方法來儘可能保證快速排序的算法性能？
答案是可以但不能完全保證。
比如我們可以採取“三點取樣”選取中值的辦法，即從數據表的第一個數據項、最後一個數據項、最中間的一個數據項這三個數據中選取不大不小的那個數據項作為中值。這樣能做一些改進，但依然無法排除極端情況。
To be continued.
