看完了分治法與遞迴，再來看這樣的方法如何解決排序問題。

快速排序是一種利用分治法的演算法，比前面提到的排序方法都要快速許多，有些程式語言的函式庫也直接包含了快速排序的函式，可以直接在實務中運用。

快速排序的步驟是：

1. 在一個數列中挑選出一個數字當作基準(pivot)。
2. 將所有比基準小的元素放前面，所有比基準大的元素放後面。
3. 用遞迴的方式，對基準兩邊的數列進行快速排序。

以實際例子來說，如果有一個數列 24, 32, 5, 45, 15, 7，第一步我們隨意挑選第一個數字24作為基準。

接下來第二個步驟叫做分割(partitioning)，將比24小的數字放前面，比24大的放後面：

5, 15, 7, 24, 32, 45

經過分割，我們會得到：比基準小的子數列(5, 15, 7)、基準(24)、比基準大的子數列(32, 45)。

接著遞迴地對子數列進行上述步驟。那麼既然是遞迴，這裡的基本情況是什麼？什麼時候問題會小到排序可以直接完成、不必再分割下去？答案就是當子數列只有0個或1個數字，可以直接當作排序完成。

所以我們將上述例子的子數列(5, 15, 7)、(32, 45)再進行挑選基準和分割，此時得到的子數列長度都<=1，遞迴結束，最後所有的數列合併可以得到排序好的數列：5, 7, 15, 24, 32, 45。

這樣的演算法以虛擬碼可以表示為：

source:維基百科

function quicksort(q)
 {
     var list less, pivotList, greater
     if length(q) ≤ 1 
         return q
     else 
     {
         select a pivot value pivot from q
         for each x in q except the pivot element
         {
             if x < pivot then add x to less
             if x ≥ pivot then add x to greater
         }
         add pivot to pivotList
         return concatenate(quicksort(less), pivotList, quicksort(greater))
     }
 }

執行時間

快速排序跟其他演算法比較不一樣的地方在於，它的執行時間跟如何挑選基準有很大的關係。

我們可以先想像，無論怎麼挑選基準，每一層遞迴都會處理陣列裡的所有元素，所以每次增加執行堆疊都會經過n次操作，這部份時間為O(n)。換句話說，執行堆疊越少，則整體執行時間越短。

基於上述所說，最壞的情況就是執行堆疊最高的情況。如果每次的基準都是陣列中最大或最小的數字，分割時就會所有元素都被分在同一邊，等於每次的子陣列只比原本少一個元素，那麼需要n-1層的遞迴才能完成排序。再乘以每層的操作時間，整個演算法的最壞情況執行時間為O(n²)。

最佳的情況，則是每次的基準都將陣列分割成兩個差不多大小的子陣列，這樣就只需要log n層遞迴。整體執行時間可以縮短為O(n log n)。

以陣列[1, 2, 3, 4, 5, 6, 7, 8]為例，如果以第一個數字作為基準，分割後會得到空陣列[]、[1]、[2, 3, 4, 5, 6, 7]，以此類推，要經過7層遞迴才能達到基本情況。但如果以4為基準，只要3層次的遞迴就可以達到基本情況。

不過快速排序的一大優勢在於，它的最佳情況執行時間也就是平均情況執行時間，也就是說一般情況下，若隨機選擇一個元素作為基準，快速排序的平均執行時間即可以達到O(n log n)。