一、概述
快速排序法是目前平均速度最快的排序法。其做法是先從原始資料中挑選「基準點」（pivot），再進行一些處理，使得比基準點小的資料都移動到左半部，比基準點大的資料在右半部。
接著再分別左、右半部做相同操作，一直遞迴下去，直到小部份沒有足夠的資料可處理為止。當對於任何一項資料，若它的前一項小於自己且後一項大於自己，就代表排序完成了。這種將問題切小再逐一解決的概念，稱為「Divide and Conquer」。
二、排序過程
假設我們有一串數值資料：4、6、8、2、5、3、7、1、9，則排序過程如下。
首先筆者選擇第一項作為基準點（pivot）。接著從第二項開始往後尋找比基準點大的下一筆資料（下圖第一列），然後從最後一項開始往前尋找比基準點小的下一筆資料。找到後將兩者交換位置，並繼續同樣的尋找與交換動作（下圖第二列）。
若遇到大、小資料都找到，但大資料的位置已超過小資料的情形（下圖第一列），則改為將基準點與小資料交換。此時會發現，基準點的左邊均為較小資料，右邊則是較大資料。接著分別對左、右半部的子集合遞迴，繼續相同的操作。
以左半部為例，仿照上述的操作方式後，子集合會排序成「1、2、3」，並以「2」為基準點切分成左、右半部（下圖第二列）。由於只剩下一筆資料，因此新的子集合就結束操作。
三、程式實作
這項排序法有交換元素的動作，因此先準備對應的程式。
private static void swap(int[] array, int index1, int index2) {
int tmp = array[index1];
array[index1] = array[index2];
array[index2] = tmp;
}
接著開始撰寫排序程式。我們宣告一個叫 sort 的方法，它會接收 startIndex 與 endIndex 的參數，針對指定的元素位置範圍進行處理。由於筆者採用範圍中的第一個元素作為基準點，故 startIndex 也等於它的位置。
private static void sort(int[] data, int startIndex, int endIndex) {
// TODO
}
在實作方面，使用 left 與 right 變數分別尋找比基準點大與小的下一項元素。left 從第二項開始，最多遞增到與 endIndex 相同。right 從最後一項開始，最少遞減到與 startIndex 相同。
private static void sort(int[] data, int startIndex, int endIndex) {
int left = startIndex + 1;
int right = endIndex;
while (true) {
while (data[left] < data[startIndex] && left < endIndex) {
left++;
}
while (data[right] > data[startIndex] && right > startIndex) {
right--;
}
// TODO
}
}
找到後，若 left 與 right 變數尚未「交錯」，就將這兩項元素交換位置。否則將基準點與 right 指向的較小元素交換，並停止尋找。此時基準點的左半部是較小元素，而右半部是較大元素。我們繼續對兩邊的子集合遞迴，做相同操作。
private static void sort(int[] data, int startIndex, int endIndex) {
int left = startIndex + 1;
int right = endIndex;
while (true) {
while (data[left] < data[startIndex] && left < endIndex) {
left++;
}
while (data[right] > data[startIndex] && right > startIndex) {
right--;
}
if (left < right) {
swap(data, left, right);
} else {
swap(data, startIndex, right);
break;
}
}
sort(data, startIndex, right - 1);
sort(data, right + 1, endIndex);
}
但遞迴的停止條件是什麼呢？我們一直都是在 startIndex 與 endIndex 所構成的位置範圍操作。此外，範圍內的元素超過一個，才有排序的必要。基於這兩點，遞迴的進行條件應為 startIndex < endIndex。顯然地，停止的條件便是 startIndex >= endIndex。當子集合切到極限，傳入的參數便會觸發這個條件。
private static void sort(int[] data, int startIndex, int endIndex) {
if (startIndex >= endIndex) {
return;
}
// 其餘略過
}
以下為快速排序法的完整程式碼
https://gist.github.com/ntub46010/905cdfb9389af61b52566db4814a3992
四、時間複雜度（最差情況）
我們先從最差情況的時間複雜度開始討論。上面的程式中使用 left 與 right 兩個指標來走訪元素們，並與基準點比較大小。如果比較次數非常多，那便是最差情況了。
在排序過程中，會將元素們切分成子集合，並對左、右半部遞迴。然而，若每次選中的基準點都是最大值或最小值，那麼就只會切出其中一邊的子集合。並且子集合的元素數量僅比上一次少了一個，所以要切很多次才會結束排序。
以「1、5、2、4、3」的原始資料為例，left 在5的位置就立刻找到比基準點1大的元素；而 right 從3的位置開始往前比較，由於無法找到比基準點小的元素，故比較4次後便到達盡頭，也就是1的位置。最後切出「5、2、4、3」的子集合，left 與 right 共比較5次。同理，接下來 left 找不到比基準點5大的元素，故比較3次後便到達3的位置。
我們歸納出，當子集合中有m個元素，這種情況的比較次數剛好為m次。因此，若原始資料有n個元素，則總比較次數為 n + (n - 1) + ... + 2 次。根據數學上等差級數的公式，計算得
[n + (n - 1) + ... + 2 + 1] - 1
= [n(n + 1) / 2] - 1
= (n² + n - 2) / 2
因此快速排序法在最差情況的時間複雜度為 O(n²)。
五、時間複雜度（最佳情況）
我們知道每切分一次子集合，其中的元素都要與所屬子集合的基準點比較大小一次，直到切到不足2個元素為止（遞迴的結束條件）。所以只要每次選中的基準點都是「中位數」，就能平均切分，讓子集合以「長度減半」的速度被切分完。
下圖是16個元素的切分示意圖，數字代表子集合的元素數量。
進行第一次切分時（遞迴深度0），扣除基準點，其中一個子集合會有7個元素，而另一個有8個。接著對子集合繼續處理（遞迴深度1），前者的子集合又被切成 3+3 個，後者被切成 3+4 個。依此類推，到達遞迴深度4，最後一個子集合被判斷不需處理，整個排序過程才結束。我們歸納出，若原始資料有n個元素，則最大遞迴深度為 log2n（小數點進位）。
經由觀察 left 與 right 兩個指標的比較次數，得知具有m個元素的子集合，兩個指標共需比較 m+1 次才會交錯，並進行下一次切分。將這項特性套用到遞迴深度 0~2，會發現比較次數都是17，即原始資料數量+1（n+1）。
至於深度3的部份，2個元素是進行排序的最小數量，任何數量的原始資料都會經歷這個過程。在時間複雜度的推導上，2個元素的處理相較於前面好幾個 n+1，只是「零頭」而已，故忽略。
最後歸納出，有n個元素的原始資料，比較次數可視為 (log2n - 2)×(n + 1)，展開算式得到「n × log2n - log2n - 2n - 2」。因此快速排序法在最佳情況的時間複雜度為 O(nlog2n)。
六、不穩定排序
當陣列中有2個相同的元素，在排序過程中，比較後面的那個是有可能被交換到更前面，使相對位置改變。但之後若它們被切分到同個子集合，還是有機會換回來的。下圖是一個例子，原始資料為：2、3、11、12，其中包含兩個「1」，我們以編號區別它們。
那什麼情況下會換不回來呢？首先我們要知道，如果陣列中只有2個相同的元素，則處理後的相對位置是不變的。因此，在切分子集合為2個元素前都還沒換回來的話，排序的結果就會失去穩定。下圖是一個例子，原始資料為：2、11、12、3。
經過以上的推演，快速排序法屬於不穩定排序。
留言
張貼留言