快速排序演算法介紹
快速排序（QuickSort）是對冒泡排序的一種改進。由 C. A. R. Hoare 在1962年提出。它的基本思想是：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。
演算法過程
設要排序的數組是 A[0] …… A[N-1]，首先任意選取一個數據（通常選用第一個數據）作為關鍵數據，然後將所有比它小的數都放到它前面，所有比它大的數都放到它後面，這個過程稱為一趟快速排序。值得注意的是，快速排序不是一種穩定的排序演算法，也就是說，多個相同的值的相對位置也許會在演算法結束時產生變動。
一趟快速排序的演算法是：
- 設置兩個變數 I、J，排序開始的時候：I = 0，J = N – 1；
- 以第一個數組元素作為關鍵數據，賦值給 key，即 key = A[0]；
- 從 J 開始向前搜索，即由後開始向前搜索（ J = J – 1），找到第一個小於 key 的值 A[ J ] ，並與 A[ I ] 交換；
- 從 I 開始向後搜索，即由前開始向後搜索（ I = I + 1 ），找到第一個大於 key 的 A[ I ]，與 A[ J ] 交換；
- 重複第3、4、5步，直到 I = J； (3,4步是在程式中沒找到時候 j = j – 1，i = i + 1，直至找到為止。找到並交換的時候 i， j 指針位置不變。另外當 i = j這過程一定正好是i+或j-完成的最後另循環結束)
上面這種演算法的描述理解起來有點繞（通過Java程式碼做了示例），但是這種演算法通過交換的方式節省了空間。在現在記憶體空間比較大的情況下，可以考慮下面這種演算法（通過Python程式碼做了示例）：
- 從數組 A 中取一個中間值 t，創建兩個數組B、C，一個（B）用來存放小於 t 的數據，另一個（C）用來存放大於 t 的數據。
- 遍曆數組 A 並與中間值 t 進行比較，將小於中間值的數據放入數組 B，將大於中間值的數據放入數組 C。
- 對數組 B、C 按照1、2步進行排序。
- 將 B、t、C組合後輸出為排序後的結果。
Java示例
class QuickSort {
public static int[] qsort(int arr[], int start, int end){
int refNumber = arr[start];
int i = start;
int j = end;
while( i < j ){
while( (i < j) && (arr[j] > refNumber) ){
j--;
}
while( (i < j) && (arr[i] < refNumber) ){
i++;
}
if( (arr[i] == arr[j]) && (i < j)){
i++;
}else{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
if( i - 1 > start) arr = qsort(arr, start, i - 1);
if( j + 1 < end ) arr = qsort(arr, j + 1 ,end);
return arr;
}
public static void main(String[] args){
int arr[] = new int[]{ 5, 10, 2, 15, 21, 99, 3, 1, 17, 23, 1, 35};
int len = arr.length - 1;
arr = qsort(arr, 0, len);
for(int i:arr){
System.out.print(i + "\t");
}
}
}
Python示例
這個演算法使用的數組支援不定長，對於其他語言來說不一定適用。
# -*- coding: utf-8 -*-
def quick_sort(data):
if len(data) >= 2: # 遞歸入口及出口
mid = data[0] # 選取基準值，也可以選取第一個或最後一個元素
left, right = [], [] # 定義基準值左右兩側的列表
data.remove(mid) # 從原始數組中移除基準值
for num in data:
if num >= mid:
right.append(num)
else:
left.append(num)
return quick_sort(left) + [mid] + quick_sort(right)
else:
return data
array = [2,3,5,7,1,4,6,15,5,2,7,9,10,15,9,17,12]
print(quick_sort(array))
# 輸出為[1, 2, 2, 3, 4, 5, 5, 6, 7, 7, 9, 9, 10, 12, 15, 15, 17]
演算法變種
快速排序(Quicksort)有幾個值得一提的變種演算法，這裡進行一些簡要介紹：
- 隨機化快排：快速排序的最壞情況基於每次劃分對主元的選擇。基本的快速排序選取第一個元素作為主元。這樣在數組已經有序的情況下，每次劃分將得到最壞的結果。一種比較常見的優化方法是隨機化演算法，即隨機選取一個元素作為主元。這種情況下雖然最壞情況仍然是O(n2)，但最壞情況不再依賴於輸入數據，而是由於隨機函數取值不佳。實際上，隨機化快速排序得到理論最壞情況的可能性僅為1/(2n)。所以隨機化快速排序可以對於絕大多數輸入數據達到O(nlogn)的期望時間複雜度。一位前輩做出了一個精闢的總結：「隨機化快速排序可以滿足一個人一輩子的人品需求。」
- 平衡快排（Balanced Quicksort）：每次儘可能地選擇一個能夠代表中值的元素作為關鍵數據，然後遵循普通快排的原則進行比較、替換和遞歸。通常來說，選擇這個數據的方法是取開頭、結尾、中間3個數據，通過比較選出其中的中值。取這3個值的好處是在實際問題（例如資訊學競賽……）中，出現近似順序數據或逆序數據的概率較大，此時中間數據必然成為中值，而也是事實上的近似中值。萬一遇到正好中間大兩邊小（或反之）的數據，取的值都接近最值，那麼由於至少能將兩部分分開，實際效率也會有2倍左右的增加，而且利於將數據略微打亂，破壞退化的結構。
- 外部快排（External Quicksort）：與普通快排不同的是，關鍵數據是一段buffer，首先將之前和之後的M/2個元素讀入buffer並對該buffer中的這些元素進行排序，然後從被排序數組的開頭（或者結尾）讀入下一個元素，假如這個元素小於buffer中最小的元素，把它寫到最開頭的空位上；假如這個元素大於buffer中最大的元素，則寫到最後的空位上；否則把buffer中最大或者最小的元素寫入數組，並把這個元素放在buffer里。保持最大值低於這些關鍵數據，最小值高於這些關鍵數據，從而避免對已經有序的中間的數據進行重排。完成後，數組的中間空位必然空出，把這個buffer寫入數組中間空位。然後遞歸地對外部更小的部分，循環地對其他部分進行排序。
- 三路基數快排（Three-way Radix Quicksort，也稱作Multikey Quicksort、Multi-key Quicksort）：結合了基數排序（radix sort，如一般的字元串比較排序就是基數排序）和快排的特點，是字元串排序中比較高效的演算法。該演算法被排序數組的元素具有一個特點，即multikey，如一個字元串，每個字母可以看作是一個key。演算法每次在被排序數組中任意選擇一個元素作為關鍵數據，首先僅考慮這個元素的第一個key（字母），然後把其他元素通過key的比較分成小於、等於、大於關鍵數據的三個部分。然後遞歸地基於這一個key位置對「小於」和「大於」部分進行排序，基於下一個key對「等於」部分進行排序。
