Table of Contents
前言
昨天介紹了第一種Divide and Conquer的演算法(Merge Sort)，今天我們要來講第二個屬於這個類別的演算法-Quick Sort。
Quick Sort的流程
相較於其他Sorting的演算法，Quick Sor算是比較特殊的一種，為什麼這麼說呢？因為經由Quick Sort執行過後的結果並非是一個正序或倒序排列的結果，反而僅僅是依照大小分為兩邊而已(如下示意圖）。
因為要依照數值大小分兩邊，就必須要有一個基準點(pivot)，然後將其他數值去跟這個pivot做比較，再分配到兩邊（如圖中的紅色和藍色的區塊）；而至於實際上數值怎麼交換位置，我們看看下面的範例好了：
在這個範例中，我們取用陣列的第一個數值作為基準點(Pivot)，然後依序從用第二個位置(i)和最後一個位置(j)的值開始進行與Pivot的比較，若兩個值都比Pivot還大，那就會從j開始一步一步往前移動，並與i的值做比較，當j的數值比i小時，i和j兩個就會交換，交換過後，再改成從i的位置一步一步往後移動，並與j的值比較，當i的值比j大時，i和j再次交換，反覆這個動作，直到i和j插肩而過（此時j在前，i在後），這兩個指標所在位置的兩個數值會交換兩次，交換兩次後，pivot的數值會再與j的數值交換位置，如此以來，Pivot的左手邊都會是比其小的數值，而右手邊則反之。Pseudo-Code在下方，請自行參閱：
function QPartition(Array[l,...,r]){
p = Array[l];
i = l;
j = r + 1;
repeat
do
i = i + 1
while Array[i] < p and i < r
do
j = j - 1
while Array[j] > p
swap(Array[i], Array[j])
until i >= j
swap(Array[i], Array[j])
swap(Array[l], Array[j])
return j
}
// Input: A subarray Array[l,...,r] of Array[0,...,n-1]
// Output: A subarray Array[l,...,r] sorted in ascending order.
function QuickSort(Array[l,...,r]){
if l < r {
// s is the index to split the array
s = QPartition(Array[l,...,r])
QuickSort(Array[l,...,s-1])
QuickSort(Array[s+1,...,r])
}
}
Quick Sort的時間複雜度
1. Best Case:
發生的情況是這個挑選的Pivot可以剛剛好將一個陣列切成左右對等長度的兩個子陣列，如此一來，其時間複雜度為𝜪(n·㏒2 n)。
2. Worst Case:
如果Pivot選擇的不好，那等於會讓某一個切出來的子陣列是空的，這種狀況通常出現在陣列已經排序過了（正序或倒序），這樣的話，期時間複雜度為𝜪(n^2)。
3. Average Case:
統計的結果是Average Case的比較次數大概會是Merge Sort的1.39倍，因此其時間複雜度為𝜪(1.39n·㏒2 n)。
小結
- Quick Sort是到目前為止介紹的Sorting演算法中唯一一個結果沒真正排序的演算法。
- Quick Sort的時間複雜度對於Best Case, Worst Case和Average Case來說都不相同。
預告
明天我們將會進入另一個主題-Transform and Conquer。