目標：將一個數組按照由低到高（或者由高到低）的順序排序。

快速排序是歷史上最著名的算法之一。1959年由 Tony Hoare 發(fā)明。

下面先來看一個比較好理解的實現版本（Kotlin）：

fun quickSort(array: IntArray): IntArray{
        if (array.size < 2) return array

        val pivot = array[array.size/2]

        val less = array.filter { it < pivot }
        val equal = array.filter { it == pivot }
        val greater = array.filter { it > pivot }

        return quickSort(less.toIntArray()) + equal + quickSort(greater.toIntArray())
    }

我們來看一看它是怎么實現的。對于給定的數組，quickSort 方法根據 “基準（pivot）”變量將它分成三部分。在上面的實現中，基準是數組的中間位置元素值（稍后我們會看到其他選取基準的方法）。

所有小于基準的元素被放到名為 less 的新數組。所有與基準值相同的元素被翻入到新數組 equal。你應該猜到，所有大于基準的元素都放入到新的數組 greater 。

一旦有了這三個數組，quickSort 數組就會遞歸對 less 和 greater 數組進行排序，然后將排序的結果和 equal 一起組合起來就是最終的排序結果。

示例

我們一起來看一個完整的排序過程。數組最初是這樣的：

[ 10, 0, 3, 9, 2, 14, 8, 27, 1, 5, 8, -1, 26 ]

首先，我們獲取基準值 8， 因為它處于數組的中間位置?，F在我們將數組分成 less，equal，greater 三個部分：

less:    [ 0, 3, 2, 1, 5, -1 ]
equal:   [ 8, 8 ]
greater: [ 10, 9, 14, 27, 26 ]

這是一次很好的拆分，因為 less 和 greater 中的元素數目大致相同。所以我們選擇了一個很好的基準將數組正好從中間分開。

注意 less 和 greater 數組還是無序的，所以我們需要繼續(xù)對這兩個數組進行快速排序。也就是再一次重復前面的事情：選取基準值，并將子數組分成3個更小的數組。

我們來看下 less 數組：

[ 0, 3, 2, 1, 5, -1 ]

基準是中間的那個元素 1。（你也可以選擇 2），再一次，我們根據這個基準創(chuàng)建了3個子數組：

less:    [ 0, -1 ]
equal:   [ 1 ]
greater: [ 3, 2, 5 ]

我們的排序還沒有完成，所以繼續(xù)遞歸對 less 和 greater 調用 quickSort 方法。我們還是來看 less 數組：

 [ 0, -1 ]

基準是 -1，現在新的子數組：

less:    [ ]
equal:   [ -1 ]
greater: [ 0 ]

less 數組是空的，因為沒有元素的值比 -1 ??；另外兩個數組各包含一個元素。這意味著我們的遞歸到這里結束，我們要回去對前面的 greater 數組進行排序。

greater 數組是：

[ 3, 2, 5 ]

和前面采取相同的處理方式，取中間位置的元素 2 作為基準：

less:    [ ]
equal:   [ 2 ]
greater: [ 3, 5 ]

注意這里我們其實應該取 3 作為基準 -- 那樣我們可以快速的完成排序，但是現在我們還要遞歸排序 greater 。這就是為什么說選擇一個好的基準是多么的重要。當你選擇了一個很糟糕的基準時，快速排序實際上會變得非常慢。

當我們分割這個 greater 數組時，我們發(fā)現：

less:    [ 3 ]
equal:   [ 5 ]
greater: [ ]

說明這一層的遞歸結束了，因為我們不能再拆分任何數組。

這一過程一直反復直到所有的子數組都已經排序完成。

Example.png

現在如果你從左往右獨處彩色標注的數字，就是我們的排序結果：

[ -1, 0, 1, 2, 3, 5, 8, 8, 9, 10, 14, 26, 27 ]

在這里 8 是一個很好的初始基準，因為在排序結果中它也是處于數組的中間位置。

我希望這個例子能夠清晰的說明快速排序是怎么工作的。不幸的是，這個版本的快速排序不能很快速的運行，因為我們每一次都要對同一個數組使用3次 filter() 函數。還有更巧妙的方法來拆分數組。

分區(qū)

將數組圍繞基準拆分的過程稱為 分區(qū)，有數種不同的分區(qū)方案。

如果數組是：

[ 10, 0, 3, 9, 2, 14, 8, 27, 1, 5, 8, -1, 26 ]

并且我們選擇中間位置的元素 8 作為基準，那么分區(qū)之后的數組是：

[ 0, 3, 2, 1, 5, -1, 8, 8, 10, 9, 14, 27, 26 ]
  -----------------        -----------------
  all elements < 8         all elements > 8

最關鍵的一點是，我們需要意識到：分區(qū)之后，基準點就已經處于最終排序結果的位置。其他的數字仍然是無序的，它們只是簡單的被分區(qū)了而已?？焖倥判驎到M進行很多次分區(qū)，直到所有的數字都處于最終的位置。

并沒有辦法保證分區(qū)能夠保持元素之間的相對位置，所以圍繞基準 8 分區(qū)之后的數組有可能是這樣的：

[ 3, 0, 5, 2, -1, 1, 8, 8, 14, 26, 10, 27, 9 ]

唯一能夠保證的是基準左邊的值都比它小，右邊的值都比它大。因為分區(qū)會改變相同元素的原始順序，快速排序不會產生“穩(wěn)定”的排序結果（這一點和其他的排序方式不通，比如歸并排序）。多數情況下這不是問題。

Lomuto 的分區(qū)方案

在前面展示的第一個版本代碼中，分區(qū)是通過調用三次 filter 函數實現的。這樣的效率并不高。所以我們一起來學習一個更巧妙的就地分區(qū)算法，通過直接修改原始數組實現。

還是先來看一個 Kotlin 版本的 Lomuto 分區(qū)：

fun partitionLomuto(a:IntArray, low: Int, high: Int): Int{
        val pivot = a[high]

        var i = low
        for ( j in low until high){
            if (a[j] <= pivot){
                swap(a, i, j)
                i++
            }
        }

        swap(a, i, high)
        return i
    }
    
fun swap(A: IntArray, x: Int, y: Int){
        val temp = A[x]
        A[x] = A[y]
        A[y] = temp
    }

然后有下面的代碼來測試一下這個分區(qū)算法：

val list = intArrayOf(10, 0, 3, 9, 2, 14, 26, 27, 1, 5, 8, -1, 8)
val p = partitionLomuto(list, 0, list.size -1)

low 和 high 兩個參數還是需要給出的，因為在快速排序的內部要使用，因為你不可能每次都對整個數組進行重新分區(qū)，你只需要在一個越來越小的范圍內分區(qū)。

前面我們使用了數組中間位置的元素作為基準，但是要注意 Lomuto 算法總是使用數組的最后一個元素作為基準。因為我們前面一直是使用 8 作為基準，所有我們在這兩個例子中將 8 和 26 的位置交換一下，所以 8 位于數組的末尾，我們仍然使用 8 作為基準。

那么分區(qū)之后，數組的內容是這樣的：

[ 0, 3, 2, 1, 5, 8, -1, 8, 9, 10, 14, 26, 27 ]
                        *

變量 p 的值就是 partitionLomuto函數的返回結果 7。這是基準元素在新數組中的位置（用 * 標注）。

現在左邊的分區(qū)就是從 0 到 p-1，也就是 [0, 3, 2, 1, 5, 8, -1]。右邊的分區(qū)是從 p+1到數組結束，也就是 [9, 10, 14, 26, 27](注意在這個例子中右半分區(qū)中的數字已經排序完成，但這只是一個巧合)。

也許你已經發(fā)現了一些有趣的事情。。。。數字 8 在這個數組中出現了不止一次。其中有一個 8 并不在數組的中間位置，而是處于左半分區(qū)。這是 Lomuto 算法的一個缺點：如果待排序數組中重復的元素太多，Lomuto 算法的運行效率將大大降低。

那么 Lomuto 算法究竟是怎么工作的呢？神奇之處在 for 循環(huán)內部。這個循環(huán)將數組分成了4個部分：

1. a[low ... i] 包含了所有小于等于基準的元素
2. a[i+1 ... j-1] 包含了所有大于基準的元素
3. a[j ... high-1] 包含了所有還沒有被分區(qū)的元素
4. a[high] 是基準的值

[ values <= pivot | values > pivot | not looked at yet | pivot ]
  low           i   i+1        j-1   j          high-1   high

循環(huán)依次檢查 low 到 high - 1 之間的元素。如果當前值比基準值小或者等于基準值，那么就通過交換位置的方式將它移到第一個區(qū)域。

循環(huán)結束之后，基準仍然是處于數組的最后，所以將它和第一個大于基準的元素交換位置，現在基準處于 <= 和 > 區(qū)域中間，并且數組已經完成分區(qū)。

來看一下完整的過程。數組開始的時候是這樣的：

[| 10, 0, 3, 9, 2, 14, 26, 27, 1, 5, 8, -1 | 8 ]
   low                                       high
   i
   j

一開始，“未分區(qū)區(qū)域”是從 index 0 到index 11，基準位于 index 12?！靶∮诘扔诨鶞蕝^(qū)域（values <= pivot）” 和 “大于基準區(qū)域（values > pivot）” 都是空的，因為我們還沒有對任何元素進行分區(qū)。

來看第一個元素 10，比基準小嗎？不是，直接跳到下一個元素。

[| 10 | 0, 3, 9, 2, 14, 26, 27, 1, 5, 8, -1 | 8 ]
   low                                        high
   i
       j

現在“未分區(qū)區(qū)域”是從index 1 到 index 11，“大于基準區(qū)域”包含數字 10，“小于基準區(qū)域”仍然是空。

現在來看第二個數字 0。比基準小嗎？是。將 10 和 0 交換，并將 i 向前移動一個位置。

[ 0 | 10 | 3, 9, 2, 14, 26, 27, 1, 5, 8, -1 | 8 ]
  low                                         high
      i
           j

現在 “未分區(qū)區(qū)域” 是從 index 2 到index 11，“大于基準區(qū)域”還是只有 10，“小于基準區(qū)域”包含數字 0。

下一個數字 3，比基準小，所以將它和 10 交換：

[ 0, 3 | 10 | 9, 2, 14, 26, 27, 1, 5, 8, -1 | 8 ]
  low                                         high
         i
             j

現在“小于區(qū)域”是 [0, 3]。繼續(xù)下一個數字 9,比基準大，直接跳過：

[ 0, 3 | 10, 9 | 2, 14, 26, 27, 1, 5, 8, -1 | 8 ]
  low                                         high
         i
                 j

現在“大于區(qū)域”是 [10, 9]。然后一直按照這個方式檢查每一個元素，那么最終的數組是：

[ 0, 3, 2, 1, 5, 8, -1 | 27, 9, 10, 14, 26 | 8 ]
  low                                        high
                         i                   j

最后要做的事情就是通過交換 a[i] 和 a[high] 將基準放入正確的位置：

[ 0, 3, 2, 1, 5, 8, -1 | 8 | 9, 10, 14, 26, 27 ]
  low                                       high
                         i                  j

并且返回 i，分區(qū)以后基準的位置。

注意：如果你對這個算法的工作原理還不清楚，我建議你手動調試一下這一段代碼，看一看每一步循環(huán)是怎么創(chuàng)建4個區(qū)域的。

現在我們使用這個分區(qū)方案來創(chuàng)建新的快速排序方法：

fun quickSortLomuto(a: IntArray, low: Int, high: Int){
        if (low < high){
            val p = partitionLomuto(a, low, high)
            quickSortLomuto(a, low, p-1)
            quickSortLomuto(a, p+1, high)
        }
    }

現在的快速排序就變得超級簡單了。我們首先調用 partitionLomuto,將數組根據基準（總是數組的最后一個元素）進行分區(qū)，然后分別對左半區(qū)和右半區(qū)遞歸調用 quickSortLomuto。

試一下：

val list = intArrayOf(10, 0, 3, 9, 2, 14, 26, 27, 1, 5, 8, -1, 8)
quickSortLomuto(list, 0, list.size - 1)

還是來看一下完整的步驟：

第一次調用時：

low = 0, high = 12
[10, 0, 3, 9, 2, 14, 26, 27, 1, 5, 8, -1, 8]

進行一次分區(qū)后：

[0, 3, 2, 1, 5, 8, -1, 8, 9, 10, 14, 26, 27]

p = 7,所以接下來對左半區(qū)進行分區(qū)，也就是：

low = 0, high = 6
[0, 3, 2, 1, 5, 8, -1, 8, 9, 10, 14, 26, 27]

分區(qū)范圍 [0, 3, 2, 1, 5, 8, -1]

下面列出對左半區(qū)進行快速排序每一次分區(qū)過程后數組內容的變化過程：

[0, 3, 2, 1, 5, 8, -1]

[-1, 3, 2, 1, 5, 8, 0]

[-1, 0, 2, 1, 5, 8, 3]

[-1, 0, 2, 1, 3, 8, 5]

[-1, 0, 1, 2, 3, 8, 5]

[-1, 0, 1, 2, 3, 5, 8]

Lomuto 算法不是唯一的分區(qū)方案，但是它可能是最容易理解的一個方案。它的效率不如 Hoare 的方案，Hoare 的分區(qū)防范會使用更少的位置交換操作。

Hoare 的分區(qū)方法

這個分區(qū)方法是由快速排序算法的作者 Hoare 發(fā)明的。

代碼如下：

fun partitionHoare(a: IntArray, low: Int, high: Int): Int {
        val pivot = a[low]
        var i = low - 1
        var j = high + 1
        while (true) {
            do {
                j--
            } while (a[j] > pivot)
            
            do {
                i++
            } while (a[i] < pivot)
            
            if (i < j) {
                swap(a, i, j)
            } else {
                return j
            }
        }
    }

可以用下面的代碼來測試一下：

val list = intArrayOf(8, 0, 3, 9, 2, 14, 10, 27, 1, 5, 8, -1, 26)
val p = partitionHoare(list, 0, list.size -1)

注意這是 Hoare 的分區(qū)方法，它總是取數組的第一個元素作為基準，即 a[low]。所以我們再次選擇 8 作為基準元素。

分區(qū)結果如下：

[ -1, 0, 3, 8, 2, 5, 1, 27, 10, 14, 9, 8, 26 ]

注意這次基準并沒有在數組的中間。和 Lomuto 的方法不同，函數的返回值并不是基準元素在新數組中的位置。

數組被分成了 [low ... p] 和 [p+1 ... high] 兩個部分。這里函數的返回結果 p 的值是6，所以兩個分區(qū)分別是 [ -1, 0, 3, 8, 2, 5, 1 ] 和
[ 27, 10, 14, 9, 8, 26 ]。

基準值處于兩個分區(qū)中的某一個地方，但是這個算法并沒有告訴你它在哪里。如果基準值的個數多于1個，那么可能有的基準值在左分區(qū)，有的在右分區(qū)。

由于這些差異，那么 Hoare 的快速排序算法實現會有點細微的差別：

fun quickSortHoare(a: IntArray, low :Int, high: Int){
       if (low < high){
           val p = partitionHoare(a, low, high)
           quickSortHoare(a, low, p)
           quickSortHoare(a, p+1, high)
       }
   }

選擇一個好的基準

Lomuto 的方法總是選擇數組的最后一個元素作為基準。Hoare 的方法使用的是數組的第一個元素作為基準。但是不能保證這些基準有任何優(yōu)點。

我們一起里看看當你選擇了一個糟糕的基準時會發(fā)生什么事情。假設有這樣一個數組：

[ 7, 6, 5, 4, 3, 2, 1 ]

我們使用 Lomuto 的方法，基準時最后一個元素 1。分區(qū)之后我們得到以下數組：

    less than pivot: [ ]
     equal to pivot: [ 1 ]
greater than pivot: [ 7, 6, 5, 4, 3, 2 ]

繼續(xù)對“大于區(qū)域”分區(qū)：

    less than pivot: [ ]
     equal to pivot: [ 2 ]
greater than pivot: [ 7, 6, 5, 4, 3 ]

繼續(xù)分區(qū)：

    less than pivot: [ ]
     equal to pivot: [ 3 ]
greater than pivot: [ 7, 6, 5, 4 ]

等等等等。。。。。

沒有任何優(yōu)點，因為這使得快速排序比插入排序還要慢得多。為了使快速排序能夠高效運行，需要將粗略的對半分開。

這個例子中最好的基準是 4，我們可以得到以下結果：

    less than pivot: [ 3, 2, 1 ]
    equal to pivot: [ 4 ]
greater than pivot: [ 7, 6, 5 ]

你可能會認為選擇數組中間位置的元素作為基準，而不是選擇第一個或者最后一個，但是想象一下下面的場景中選擇中間位置的元素會發(fā)生什么：

[ 7, 6, 5, 1, 4, 3, 2 ]

由于現在選擇中間的 1 作為基準，結果和前面的例子一樣糟糕。

理想情況下，應該選擇倒排序數組中所有元素的中位數作為基準。即：基準應該處于排序后數組的中間位置。當然，在完成排序之前，你并不知道中位數是什么，所以這有點像“先有雞還是先有蛋”的問題。但是，總有一些技巧來選擇一個更好（如果不是最理想）的基準。

技巧之一就是 "三數取中"，即取數組第一個元素、中間元素以及最后一個元素三者的中位數。理論上，這個方法常常會給出真實中位數很好的近似值。

另外一個常用的方法就是隨機選擇基準。這個方法有時會給出一個的次優(yōu)的基準，但是一般情況下都會給出一個非常好的結果。

我們來看看怎么通過隨機選擇基準的方式實現快速排序：

fun quickSortRandom(a: IntArray, low: Int, high: Int){
        if (low < high){
            val ran = Random()
            val pivotIndex = low + Math.abs(ran.nextInt())%(high - low) // 1
            swap(a, pivotIndex,high)    //2

            val p = partitionLomuto(a, low, high)
            quickSortRandom(a, low, p -1)
            quickSortRandom(a, p+1, high)
        }
    }

這里有兩個重要的地方和前面的實現不一樣：

1. 通過隨機函數獲取到一個介于 low 和 high 之間的隨機數，也就是我們基準元素的位置index。
2. 由于 Lomuto 是使用最后一個元素作為基準，所以我們在調用partitionLomuto之前交換了 a[pivotIndex] 和 a[high] 的位置。

也許在一個排序函數中使用隨機數看起來有點奇怪，但是保證快速排序在所有的情況下都能高效工作是很有必要的。如果選擇了一個糟糕的基準，快速排序的性能會非?？植?，O(n^2)。但是如果多數情況都是選擇了一個好的基準，比如通過使用隨機數生成器，那么時間復雜度就會降為O(n log n)，這是一個好的排序算法應該達到的性能。

本文譯自 swift-algorithm-club