目标：将一个数组按照由低到高（或者由高到低）的顺序排序。

快速排序是历史上最著名的算法之一。1959年由 Tony Hoare 发明。

下面先来看一个比较好理解的实现版本（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， 因为它处于数组的中间位置。现在我们将数组分成 less，equal，greater 三个部分：

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

这是一次很好的拆分，因为 less 和 greater 中的元素数目大致相同。所以我们选择了一个很好的基准将数组正好从中间分开。

注意 less 和 greater 数组还是无序的，所以我们需要继续对这两个数组进行快速排序。也就是再一次重复前面的事情：选取基准值，并将子数组分成3个更小的数组。

我们来看下 less 数组：

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

基准是中间的那个元素 1。（你也可以选择 2），再一次，我们根据这个基准创建了3个子数组：

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

我们的排序还没有完成，所以继续递归对 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 数组时，我们发现：

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

说明这一层的递归结束了，因为我们不能再拆分任何数组。

这一过程一直反复直到所有的子数组都已经排序完成。

Example.png

现在如果你从左往右独处彩色标注的数字，就是我们的排序结果：

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

在这里 8 是一个很好的初始基准，因为在排序结果中它也是处于数组的中间位置。

我希望这个例子能够清晰的说明快速排序是怎么工作的。不幸的是，这个版本的快速排序不能很快速的运行，因为我们每一次都要对同一个数组使用3次 filter() 函数。还有更巧妙的方法来拆分数组。

分区

将数组围绕基准拆分的过程称为 分区，有数种不同的分区方案。

如果数组是：

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

并且我们选择中间位置的元素 8 作为基准，那么分区之后的数组是：

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

最关键的一点是，我们需要意识到：分区之后，基准点就已经处于最终排序结果的位置。其他的数字仍然是无序的，它们只是简单的被分区了而已。快速排序会对数组进行很多次分区，直到所有的数字都处于最终的位置。

并没有办法保证分区能够保持元素之间的相对位置，所以围绕基准 8 分区之后的数组有可能是这样的：

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

唯一能够保证的是基准左边的值都比它小，右边的值都比它大。因为分区会改变相同元素的原始顺序，快速排序不会产生“稳定”的排序结果（这一点和其他的排序方式不通，比如归并排序）。多数情况下这不是问题。

Lomuto 的分区方案

在前面展示的第一个版本代码中，分区是通过调用三次 filter 函数实现的。这样的效率并不高。所以我们一起来学习一个更巧妙的就地分区算法，通过直接修改原始数组实现。

还是先来看一个 Kotlin 版本的 Lomuto 分区：

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
    }

然后有下面的代码来测试一下这个分区算法：

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 两个参数还是需要给出的，因为在快速排序的内部要使用，因为你不可能每次都对整个数组进行重新分区，你只需要在一个越来越小的范围内分区。

前面我们使用了数组中间位置的元素作为基准，但是要注意 Lomuto 算法总是使用数组的最后一个元素作为基准。因为我们前面一直是使用 8 作为基准，所有我们在这两个例子中将 8 和 26 的位置交换一下，所以 8 位于数组的末尾，我们仍然使用 8 作为基准。

那么分区之后，数组的内容是这样的：

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

变量 p 的值就是 partitionLomuto函数的返回结果 7。这是基准元素在新数组中的位置（用 * 标注）。

现在左边的分区就是从 0 到 p-1，也就是 [0, 3, 2, 1, 5, 8, -1]。右边的分区是从 p+1到数组结束，也就是 [9, 10, 14, 26, 27](注意在这个例子中右半分区中的数字已经排序完成，但这只是一个巧合)。

也许你已经发现了一些有趣的事情。。。。数字 8 在这个数组中出现了不止一次。其中有一个 8 并不在数组的中间位置，而是处于左半分区。这是 Lomuto 算法的一个缺点：如果待排序数组中重复的元素太多，Lomuto 算法的运行效率将大大降低。

那么 Lomuto 算法究竟是怎么工作的呢？神奇之处在 for 循环内部。这个循环将数组分成了4个部分：

1. a[low ... i] 包含了所有小于等于基准的元素
2. a[i+1 ... j-1] 包含了所有大于基准的元素
3. a[j ... high-1] 包含了所有还没有被分区的元素
4. a[high] 是基准的值

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

循环依次检查 low 到 high - 1 之间的元素。如果当前值比基准值小或者等于基准值，那么就通过交换位置的方式将它移到第一个区域。

循环结束之后，基准仍然是处于数组的最后，所以将它和第一个大于基准的元素交换位置，现在基准处于 <= 和 > 区域中间，并且数组已经完成分区。

来看一下完整的过程。数组开始的时候是这样的：

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

一开始，“未分区区域”是从 index 0 到index 11，基准位于 index 12。“小于等于基准区域（values <= pivot）” 和 “大于基准区域（values > pivot）” 都是空的，因为我们还没有对任何元素进行分区。

来看第一个元素 10，比基准小吗？不是，直接跳到下一个元素。

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

现在“未分区区域”是从index 1 到 index 11，“大于基准区域”包含数字 10，“小于基准区域”仍然是空。

现在来看第二个数字 0。比基准小吗？是。将 10 和 0 交换，并将 i 向前移动一个位置。

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

现在 “未分区区域” 是从 index 2 到index 11，“大于基准区域”还是只有 10，“小于基准区域”包含数字 0。

下一个数字 3，比基准小，所以将它和 10 交换：

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

现在“小于区域”是 [0, 3]。继续下一个数字 9,比基准大，直接跳过：

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

现在“大于区域”是 [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，分区以后基准的位置。

注意：如果你对这个算法的工作原理还不清楚，我建议你手动调试一下这一段代码，看一看每一步循环是怎么创建4个区域的。

现在我们使用这个分区方案来创建新的快速排序方法：

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,将数组根据基准（总是数组的最后一个元素）进行分区，然后分别对左半区和右半区递归调用 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]

进行一次分区后：

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

p = 7,所以接下来对左半区进行分区，也就是：

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

分区范围 [0, 3, 2, 1, 5, 8, -1]

下面列出对左半区进行快速排序每一次分区过程后数组内容的变化过程：

[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 算法不是唯一的分区方案，但是它可能是最容易理解的一个方案。它的效率不如 Hoare 的方案，Hoare 的分区防范会使用更少的位置交换操作。

Hoare 的分区方法

这个分区方法是由快速排序算法的作者 Hoare 发明的。

代码如下：

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 的分区方法，它总是取数组的第一个元素作为基准，即 a[low]。所以我们再次选择 8 作为基准元素。

分区结果如下：

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

注意这次基准并没有在数组的中间。和 Lomuto 的方法不同，函数的返回值并不是基准元素在新数组中的位置。

数组被分成了 [low ... p] 和 [p+1 ... high] 两个部分。这里函数的返回结果 p 的值是6，所以两个分区分别是 [ -1, 0, 3, 8, 2, 5, 1 ] 和
[ 27, 10, 14, 9, 8, 26 ]。

基准值处于两个分区中的某一个地方，但是这个算法并没有告诉你它在哪里。如果基准值的个数多于1个，那么可能有的基准值在左分区，有的在右分区。

由于这些差异，那么 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 的方法使用的是数组的第一个元素作为基准。但是不能保证这些基准有任何优点。

我们一起里看看当你选择了一个糟糕的基准时会发生什么事情。假设有这样一个数组：

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

我们使用 Lomuto 的方法，基准时最后一个元素 1。分区之后我们得到以下数组：

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

继续对“大于区域”分区：

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

继续分区：

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

等等等等。。。。。

没有任何优点，因为这使得快速排序比插入排序还要慢得多。为了使快速排序能够高效运行，需要将粗略的对半分开。

这个例子中最好的基准是 4，我们可以得到以下结果：

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

你可能会认为选择数组中间位置的元素作为基准，而不是选择第一个或者最后一个，但是想象一下下面的场景中选择中间位置的元素会发生什么：

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

由于现在选择中间的 1 作为基准，结果和前面的例子一样糟糕。

理想情况下，应该选择倒排序数组中所有元素的中位数作为基准。即：基准应该处于排序后数组的中间位置。当然，在完成排序之前，你并不知道中位数是什么，所以这有点像“先有鸡还是先有蛋”的问题。但是，总有一些技巧来选择一个更好（如果不是最理想）的基准。

技巧之一就是 "三数取中"，即取数组第一个元素、中间元素以及最后一个元素三者的中位数。理论上，这个方法常常会给出真实中位数很好的近似值。

另外一个常用的方法就是随机选择基准。这个方法有时会给出一个的次优的基准，但是一般情况下都会给出一个非常好的结果。

我们来看看怎么通过随机选择基准的方式实现快速排序：

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