快速排序法
簡介
快速排序法（Quicksort）平均效率為O(n log n)，即排序N個項目需要（nlogn）次比較，而最壞的情況下需要比較 n2 次，綜合表現比其他同樣效率為O(nlogn)的算法快，是目前最快的算法。
原理
1. 從數列（array）隨意選一個元素（element），設定此元素為基準（pivot） 2. 把所有數值比基準值小的元素放在基準值前面；把所有數值比基準值大的放在基準值後面 3. 使用遞歸法（recursion）不斷循環排序，把比基準值少的數列和比基準值大的數列分別再一次排序 4. 兩批數列分別成立了兩個分區（partition）註：這個算法跟合併排序（Merge sort）不一樣，不用把兩個數列合併成一個數列。
算法
快速排序法採用分治法（Divide and Conquer），把一個數列分為兩個子數列。 1. 定義一個頭（first）和一個尾（last），分別為數列最左邊和最右邊的數字 2. 隨機定義一個基準值，或者人工設定一個這個基準值如（first + last）/2快速排序法的偽代碼（Pseudocode）是
Divide and Conquer /** num: the array containing the array of numbers to be sorted* first: the left most number in the array a* last: the right most number in the array a* pivot: an integer indicating the position of the point separating two partitions*/function Quicksort(array num, int first, int last) { IF (first < last) {pivot = Partition(num, first, last) } Quicksort(num, first, pivot-1) Quicksort(num, pivot+1, last)}
/** Purpose: return the position of pivot*/function Partition(array num, int first, int last) { pivot = num[first] left = first // left: an index indicating the position of number in the array num right = last
While (left < right) { increment left until (num[left] > pivot) or (left > right) decrement right until (num[right] < pivot)or(left>right) IF (left < right) { Swap num[left] and num[right] } pivot = right Swap num[left] and data[pivot] Return pivot }}
效率
平均：O（nlogn)
當基準值是數列的中值（median），這樣兩個分區便擁有相同數量的元素，這樣就原來的數列分成 log N個分區，然後每個分區進行N次比對，。
最差：O（n2 ）
當基準值為最大值或最小值時，兩個分區其中一個便沒有任何元素。
總結
快速排序法是目前平均最快的算法，而且不需像合併排序般要求額外的存儲空間來暫存複製過來的數列，又不用像其他算法般把整個數列複製，節省存儲空間和抄送數列的時間。不過，快速排序法的最差情況效率為O(nlogn)，而合併排序保證所有情況的效率均為O(nlogn)，因此快速排序法不會用作。
