從設計演算法角度理解快速排序

什麼是快速排序？

快速排序（Quicksort）又名劃分-交換排序（Partition-exchange sort）， 平均複雜度為O(N*logN），較常用的排序演算法，最早由托尼·霍爾提出

快速排序的思想及其原理

快速排序主要用到兩個思想： 1. 分區（partiton） 2. 遞歸（recursion） （在有的教程中甚至將快排函數分成「分區」和「遞歸」兩個函數來寫）

快速排序中的每次排序先將大的問題進行順序分區處理，使第一次處理後的序列中有一個數左側都是比它小的數，右邊都是比它大的數，再對數組的左右兩部分執行同樣的操作（即進行遞歸），最終達到排序的效果。

根據快排的思想實現分區演算法（關鍵）

假設現在我們是托尼·霍爾，我們從一根香蕉中得到了靈感，了解了快速排序的思想原理，那麼我們應該怎麼樣設計分區演算法呢？

首先我們應該考慮我們想要得到的效果，換句話說，我們應該怎樣實現「使比X小的元都在X左側，比X大的都在X右側」？

我們可以確定我們至少要做兩件事，第一我們肯定需要比較，第二因為數組中的所有數都要滿足條件，所以我們還需要一個循環，用來對每一個數進行比較。

我們可以試著寫寫偽碼了:

for each 數 in 數組: if 數 < X: 把數放在X左邊 else: 把數放在X右邊

好了現在我們考慮的問題只有如何實現「把數放在X左/右邊」啦！

我們第一反應可能是新建兩個鏈表（因為不確定X左右邊數的個數）用來存放less和greater，如果你想到這裡，恭喜你完成了快速排序的初級版本！（見維基百科-快速排序-演算法）

但是這個簡單的快速排序會額外浪費Ω(N)的空間，所以我們要想想辦法不新開數組或鏈表，而是在原地（in place）實現「把合適的數放在X左/右」。

既然我們要在原地進行排序，在選擇X時，有必要把X選在數組的最左側或者最右側，減少思考不同情況時引起的思維混亂。

栗子：

X5 1 3 2 6 4

選定X在最右側以後，我們就可以不用考慮X的位置，暫且把它當成一個數組外的數，只對前面的數進行處理。

我們需要建立一個循環用以詢問每個數，但是當我們遇到一個小於或大於X的數時，我們應該怎麼處理它呢？

當然是把小於X的數盡量往左扔，大於X的盡量往右扔。

但是為了不覆蓋其他的數，我們應該採用交換（swap）的方式調整位置。所以我們至少需要兩個記錄位置的變數用於交換，一個（i）記錄比X小的數，一個（j）記錄比X大的數。

i j X5 1 3 2 6 4 (排序過程中的某狀態)

現在又出現了新的問題：由於採用的是交換位置的方式，怎樣確定我們把較小的數換過去後，換來的是較大的數？有兩種解決方案：

1. 使i，j從同一起點出發，由j進行遍歷，遇到比X大的數就繼續(j++)，遇到比X的小的數就進行swap(arr[j], arr[i])。由於i跟在j的後面，從而保證了arr[i] <= arr[j]。PS：為了arr[j]不重複與同一個數交換swap以後需要i++向前推進

我們來驗證一下，順便完善細節：

i,j X5 1 3 2 6 4顯然arr[j] > X，所以j向前移動1i j X5 1 3 2 6 4此時arr[j] < X，swap(arr[i], arr[j])然後i，j向前移動 i j X1 5 3 2 6 4再次出現arr[j] < X，步驟同上 i j X1 3 5 2 6 4繼續同上 i j X1 3 2 5 6 4除X外其餘數已經分好了區

由於已經保證arr[i] <= arr[j]，下一步可swap(arr[i], arr[X])

<X X >X1 3 2 4 6 5

1. 另一種解決方案是使i和j開始狀態時其中一個為空，這樣swap(arr[i], arr[j])時，因為交換過去了空位置，只要每次都交換空位置，最後再將合適的數填進去，就可以保證有效的swap。

但這個空位置怎麼來呢？我們上文已經想到「讓X盡量晚參與分區」，於是我們可以把X保存在另一個變數中，X的原位就可以視為空了。

假設我們選擇j在這個空位置，那麼i的循環就有兩種選擇：

• i的初始位置在另一端，當i和j接觸時遍歷完成
• i的初始位置緊挨j，當i遍歷到數組一端時遍歷完成

我們以第一種為例

具體細節可以邊實驗邊補充：

i j X = 45 1 3 2 6 （4可視為空）我們從i開始遍歷（判定），第一個遇到的數就不符合arr[i] < X，swap，然後i，j都前進 i j X = 4空 1 3 2 6 5接著j開始遍歷（判定），符合，do nothing，繼續前進 i j X = 4空 1 3 2 6 5i判定符合，繼續前進 i j X = 4空 1 3 2 6 5j不符合判定，與空位置交換 2 1 3 空 6 5此時i，j接觸，遍歷結束。因為i經過的地方都保證小於X，j經過的地方都大於X，所以空位填X正好符合條件 <X X >X2 1 3 4 6 5

OK，完成了對原始數組的分區

遞歸

接下來就很好理解了，只需對X左右的兩部分做相同的事就可以了

base case就是數組長度小於等於1了

實現

C/C++

void quick_sort(int arr[], int left, int right){ int x_index = right; int i = left; int j = left; if ((right - left) < 1) { return; } while(j <= right) { if (arr[j] > arr[x_index]) { j++; } else { swap(arr[i++], arr[j++]); } } quick_sort(arr, left, i - 2); quick_sort(arr, i, right);}

與其他演算法設計思路的比較

與歸併排序（使用遞歸先將大的，不易解決的問題劃分成小問題再開始解決）不同，快排起手先部分解決問題，再進行遞歸對其部分進行處理，最終使得問題全部解決。雖然都是遞歸，設計思路有些不同。