快速排序（Quick Sort）

快速排序是另一种基于比较的排序方法，和归并排序有些类似，都是使用分割和合并的策略。

快速排序最重要的特点是会选择一个轴点，这个轴点将数组分割成3段：

  [elements < pivot | pivot | elements > pivot ]

示例

我们来看一个快速排序的简单实现

public func quicksortNaive<T: Comparable>(_ a: [T]) -> [T] {
  guard a.count > 1 else { // 1
    return a
  }
  let pivot = a[a.count / 2] // 2
  let less = a.filter { $0 < pivot } // 3
  let equal = a.filter { $0 == pivot }
  let greater = a.filter { $0 > pivot }
  return quicksortNaive(less) + equal + quicksortNaive(greater) // 4
} 

以上的递归函数调用将数组分成了3部分，流程大概是这样：
1，确保数组元素的数量大于1个，相反，就只有一个元素，就已经是有序的了。
2，将数组中间的元素作为自己的轴点。
3，以这个元素为轴点，将原数组分为三部分，小于轴点，轴点和大于轴点的部分。
4，对每部分递归分割方法并且重新组合他们。
给定以下未排序数组：

[12, 0, 3, 9, 2, 18, 8, 27, 1, 5, 8, -1, 21 ]
                     *

在该实现中，总是选择中间的元素作为轴点，在这个例子中，把元素8作为轴点，分成的3部分为：

less: [0, 3, 2, 1, 5, -1]
equal: [8, 8]
great: [12, 9, 18, 27, 21]

注意看，这三部分并不是完全有序的，快速排序会递归的将这三部分分成更小的部分。直到被隔成只有1个或者0个元素时，递归调用才会停止。下图是整个分割过程的总揽：

quickSort1.png

对每一层的数据递归调用快速排序，当递归调用结束时，把树叶组合起来，就得到了完整的有序数组。

[-1, 1, 2, 3, 5, 8, 8, 9, 12, 18, 21, 27]

虽然刚才快速排序的实现非常容易理解，但在该实现中有一些问题：

• 对同一个数组调用三次 filter 方法效率很低。
• 创建一个新的数组来保存每一部分，空间的效率不高，有更合适的进行分类么？
• 把中间的元素当作轴点是最好的选择么，合适的轴点应该具备哪些特点呢。

分割策略

在这部分，你将看到更高效的快速排序实现。第一个分割算法叫作：Lomuto’s algorithm.

Lomuto’s分割

Lomuto’s分割总是将最后一个元素作为轴点。接下来我们使用代码来实现该算法：

public func partitionLomuto<T: Comparable>(_ a: inout [T],
                                           low: Int,
                                           high: Int) -> Int {
}

该函数有3个参数：

• a 是分割的数组。
• low 和 high 是分割范围的最大索引和最小索引，在每一次递归调用时，分割范围会变得越来越小。

这个函数返回轴点的索引。
现在在该函数中添加如下实现：

let pivot = a[high] // 1

var i = low // 2
for j in low..<high { // 3
  if a[j] <= pivot { // 4
    a.swapAt(i, j) // 5
    i += 1
  }
}

a.swapAt(i, high) // 6
return i // 7

从以上函数可以看出：
1，Lomuto 始终将每部分的最后一个元素作为轴点。
2，变量i 表示有多少元素小于轴点，当遇到比轴点元素小的元素就交换，并使i 加1。
3，遍历整个数组从 low 到 high，但不包含 high，因为high点是轴点元素。
4，检查当前元素是否小于或等于该轴点元素。
5，如果条件成立，就交换i处的元素，并使 i 值加1。
6，当循环遍历结束时，交换i处和 轴点的值。这样的话，这个轴点元素会在 小于部分和大于部分之间。
7，返回轴点的索引。
当用这种算法遍历数组时，其将数组分成了4部分：
1，a[low..<I] 包含了所有 <= pivot 的元素。
2，a[i...j-1] 包含了所有 > pivot 的元素。
3，a[j...high - 1] 该区间的值是未进行比较的元素。
4，a[high] 是轴点元素。

[ values <= pivot | values > pivot | not compared yet | pivot ]
low          i-1    I        j - 1    j       high - 1    high

逐步分析：
通过一步步的对该算法进行分析，从而对该算法有一个更清楚的认识。

假定以下未排序数组：

[12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 8]

首先，把最后一个元素 8 选为 轴点

[ 12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, |  8  ]
  low                                        high
  i
  j

然后，第一个元素12和轴点元素进行比较，由于 12 > 8 ，所以继续对下一个元素进行比较。

  0  1  2  3  4  5   6   7   8  9  10  11   12
[ 12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, |  8  ]
  low                                        high
  i
      j

第二个元素0比轴点元素小，所以将索引 i 处和 j 处元素进行交换，并使 i + 1 ：

  0   1  2  3  4  5   6   7   8  9  10  11   12
[ 0, 12, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, |  8  ]
 low                                         high
      i
         j

第三个元素3同样比轴点元素小，所以和上一次执行一样的交换操作：

  0   1  2  3  4  5   6   7   8  9  10  11   12
[ 0, 3, 12, 9, 2, 21, 18, 27, 1, 5, 8, -1, |  8  ]
 low                                         high
         i
            j

重复以上步骤直到除了pivot元素，全都比较了一遍。最终数组为：

  0   1  2  3  4  5   6   7   8  9  10  11   12
[ 0, 3, 2, 1, 5, 8, -1, 27, 9, 12, 21, 18, |  8  ]
 low                                         high
                         i

最后，轴点元素和 索引 i 处的元素进行交换。

  0   1  2  3  4  5   6   7   8  9  10  11     12
[ 0, 3, 2, 1, 5, 8, -1 | 8 | 9, 12, 21, 18, |  27  ]
 low                                          high
                         i

以上就是Lomuto’s分割的全部了。需要注意的是观察轴点元素如何将数组分隔的。

接下来我们就可以将 quicksort 方法进行完善

public func quicksortLomuto<T: Comparable>(_ a: inout [T], low: Int, high: Int) {
  if low < high {
    let pivot = partitionLomuto(&a, low: low, high: high)
    quicksortLomuto(&a, low: low, high: pivot - 1)
    quicksortLomuto(&a, low: pivot + 1, high: high)
  }
}

Hoare's partitioning

霍尔分割总是选择第一个元素作为轴点，接下来，让我们使用代码实现该过程。

public func partitionHoare<T: Comparable>(_ a: inout [T], low: Int, high: Int) -> Int {
  let pivot = a[low] // 1
  var i = low - 1 // 2
  var j = high + 1

  while true {
    repeat { j -= 1 } while a[j] > pivot // 3
    repeat { i += 1 } while a[i] < pivot // 4

    if i < j { // 5
      a.swapAt(i, j)
    } else {
      return j // 6
    }
  }
}

1，选择第一个元素作为轴点。
2，索引 i 和 j 定义了两个区域，小于索引 i 的元素都是 小于 或者等于该轴点的元素。在 索引 j 后面的元素都是大于或者等于该轴点的元素。
3，让 j 自减，直到元素值不在大于轴点值。
4，让 i 自增，直到元素值不在小于轴点值。
5，如果 i 和 j 没有重叠，交换两个元素。
6，返回该索引，使用该索引，对区域进行分割。

逐步分析

给定以下数组：

[  12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 8   ]

首先，把12设置为轴点元素，然后 i 和 j 将开始自增和自减，知道到查找小于或者大于该轴点的元素。一开始，i 将会在 12 处停住，j 将会在 8 处停住。

[  12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1,  8  ]
   p
   i                                         j

12 和 8 进行交换：

[  8, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 12 ]
   i                                       j

i 和 j 现在继续移动，这次停在 21 和 -1 处：

[  8, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 12 ]
                   i                    j 

然后交换两个值：

[  8, 0, 3, 9, 2, -1, 18, 27, 1, 5, 8, 21, 12 ]
                   i                    j

接下来，18 和 8 进行交换，交换完，27 和 5 进行交换。

经过交换后，数组变成了以下形式：

[  8, 0, 3, 9, 2, -1, 8, 5, 1, 27, 18, 21, 12 ]
                         i      j

接下来，继续移动 i 和 j ,他们将会重叠：

[  8, 0, 3, 9, 2, -1, 8, 5, 1, 27, 18, 21, 12 ]
                            j   i

霍尔分割整个过程就是这样了，然后将 j作为两个区域的分割线返回。
相比于 Lomuto 算法，霍尔分割的交换操作少。

public func quicksortHoare<T: Comparable>(_ a: inout [T], low: Int, high: Int) {
  if low < high {
    let p = partitionHoare(&a, low: low, high: high)
    quicksortHoare(&a, low: low, high: p)
    quicksortHoare(&a, low: p + 1, high: high)
  }
}

选择错误轴点的影响

在快速排序中最重要的策略是选择正确的轴点。
以下是3中不同的分割策略：
1，选择中间的元素作为轴点。
2，Lomuto,其他以最后一个元素作为轴点的算法。
3，Hoare, 其他以第一个元素作为轴点的算法。

选择了一个坏的轴点有什么坏处呢？

我们来看下以下未排序的的数组：

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

假如将 最后一个元素作为轴点，就会导致如下的分割情况：

less: [ ]
equal: [1]
greater: [8, 7, 6, 5, 4, 3, 2] 

一个理想的轴点，会均匀的将小于轴点的部分和大于轴点的部分进行分割。对已经排好序的数组来说，选择第一个或者最后一个元素作为轴点，会使得快速排序更像插入排序，会导致最坏的时间复杂度为 O(n²) 。解决该问题的一个方法为 采用 median of three 的方法选取轴点。将数组中的第一个，中间的，和最后一个元素的中间值最为轴点，这就避免了选择了数组中的最大值或者最小值作为轴点了。

public func medianOfThree<T: Comparable>(_ a: inout [T], low: Int, high: Int) -> Int {
  let center = (low + high) / 2
  if a[low] > a[center] {
    a.swapAt(low, center)
  }
  if a[low] > a[high] {
    a.swapAt(low, high)
  }
  if a[center] > a[high] {
    a.swapAt(center, high)
  }
  return center
}

你可以看出来通过 a[low],a[center]和 a[high]进行排序，会在center索引处停止。

接下来，我们来实现通过 median of three 变种而来的排序算法

public func quickSortMedian<T: Comparable>(_ a: inout [T], low: Int, high: Int) {
  if low < high {
    let pivotIndex = medianOfThree(&a, low: low, high: high)
    a.swapAt(pivotIndex, high)
    let pivot = partitionLomuto(&a, low: low, high: high)
    quicksortLomuto(&a, low: low, high: pivot - 1)
    quicksortLomuto(&a, low: pivot + 1, high: high)
  }
}

最后附上本文的相关代码DataAndAlgorim

参考链接《Data Structures & Algorithms in Swift》