34.快速排序¶

在前面的章节中，你已经学会了使用基于比较的排序算法对数组进行排序，例如合并排序和堆排序。

Quicksort是另一种基于比较的排序算法。与合并排序很相似，它使用相同的divide and conquer策略。快速排序的一个重要特征是选择一个pivot。支点将数组划分为三个部分：

[ elements < pivot | pivot | elements > pivot ]

在本章中，你将实现quicksort，并研究各种分区策略，以充分利用这种排序算法。

示例¶

打开启动器的playground。在quicksortNaive.swift中提供了quicksort的天真实现：

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
}

上面的实现是递归地将数组过滤成三个分区。我们来看看它是如何工作的：

数组中必须有一个以上的元素。如果没有，数组被认为是被排序的。
选择数组中的middle元素作为你的支点。
利用这个支点，将原数组分成三个部分。枢轴上的元素less than、equal to或greater than进入不同的桶中。
递归排序，然后合并这些分区。

现在让我们把上面的代码可视化。给出下面的unsorted数组：

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

在这个实现中，你的分区策略是总是选择middle元素作为支点。在这个例子中，这个元素是8。使用这个支点对数组进行分区，会产生以下分区：

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

Note

这三个分区还没有完全排序。Quicksort将递归地把这些分区分成更小的分区。递归只有在所有分区都有零或一个元素时才会停止。

下面是所有分区步骤的概述：

每一层都对应着对quicksort的递归调用。一旦递归停止，叶子就会被再次合并，从而得到一个完全排序的数组：

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

虽然这种幼稚的实现方式很容易理解，但它提出了一些问题和疑问：

在同一个数组上调用filter三次并不高效。
为每个分区创建一个新的数组并不节省空间。你能不能在原地排序？
挑选中间的元素是最好的支点策略吗？你应该采用什么支点策略？

分区策略¶

在这一节中，你将研究分区策略和使quicksort的实现更有效率的方法。你要看的第一个分区算法是Lomuto’s algorithm。

`Lomuto`的分区算法¶

Lomuto的分区算法总是选择last的元素作为支点。让我们看看这在代码中是如何工作的。

在你的playground上，创建一个名为quicksortLomuto.swift的文件，并添加以下函数声明：

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

这个函数需要三个参数：

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

以下是这段代码的作用：

设置支点。Lomuto总是选择最后一个元素作为支点。
变量i表示有多少个元素比支点少。当你遇到一个小于中枢的元素时，将其与索引为i的元素交换，并增加i。
循环浏览从low到high的所有元素，但不包括high，因为它是枢纽。
检查当前元素是否小于或等于中枢。
如果是，将其与索引i的元素交换，并增加i。
循环结束后，将i处的元素与支点交换。枢轴总是位于less和greater两个部分之间。
返回支点的索引。

当这个算法在数组中循环时，它将数组划分为四个区域：

a[low...<i]包含所有<= pivot的元素。
a[i...j-1]包含所有大于pivot的元素。
a[j...high-1]是你还没有比较的元素。
a[high]是支点元素。

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

循序渐进¶

看一下该算法的几个步骤，以清楚地了解它是如何工作的。给出下面的unsorted数组：

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

首先，最后一个元素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

然后，第一个元素，12，与中枢进行比较。它不比中枢小，所以算法继续到下一个元素：

   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的元素（12）交换，i被增加：

  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

这些步骤一直持续到除枢轴元素之外的所有元素都被比较。由此产生的数组是：

  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的分区现在已经完成。注意支点是如何位于小于或等于支点的元素和大于支点的元素这两个区域之间的。

在quicksort的天真实现中，你创建了三个新数组，并对未排序的数组进行了三次过滤。Lomuto的算法则是在原地执行分区。这样效率就高多了!

有了你的分区算法，你现在可以实现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)
  }
}

在这里，你应用Lomuto算法将数组划分为两个区域；然后，你递归地对这些区域进行排序。一旦一个区域的元素少于两个，递归就会结束。

你可以通过在你的playground上添加以下内容来尝试Lomuto的quicksort：

var list = [12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 8]
quicksortLomuto(&list, low: 0, high: list.count - 1)
print(list)

`Hoare`分区法¶

Hoare的分区算法总是选择first元素作为支点。让我们看看这在代码中是如何工作的。

在你的playground上，创建一个名为quicksortHoare.swift的文件，并添加以下函数：

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
    }
  }
}

让我们来看看这些步骤：

选择第一个元素作为支点。
索引i和j定义了两个区域。i之前的每个索引都将less than or equal to支点。j之后的每个索引将greater than or equal to中枢。
减少j，直到它到达一个不大于枢轴的元素。
增加i，直到它到达一个不小于枢轴的元素。
如果i和j没有重叠，交换元素。
返回分隔两个区域的索引。

Note

从分区返回的索引不一定是枢轴元素的索引。

分解步骤¶

给出下面的unsorted数组：

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

首先，12被设置为支点。然后i和j将开始在数组中运行，寻找不小于（如果是i）或大于（如果是j）中枢的元素。i将停止在元素12，j将停止在元素8：

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

然后这些元素被调换：

[  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

The next time you move i and j, they will overlap:

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

Hoare的算法现在完成了，索引j被返回作为两个区域之间的分离。与Lomuto的算法相比，这里的交换要少得多。这不是很好吗？

现在你可以实现一个quicksortHoare函数：

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)
  }
}

通过在你的playground上添加以下内容进行尝试：

var list2 = [12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 8]
quicksortHoare(&list2, low: 0, high: list.count - 1)
print(list2)

糟糕的支点选择的影响¶

实现quicksort的最关键部分是选择正确的分区策略。

你已经看了三种不同的分区策略：

选择中间的元素作为支点。
Lomuto，或选择最后一个元素作为枢纽。
Hoare，即选择第一个元素作为支点。

选择一个不好的支点会有什么影响？

让我们从下面这个未排序的数组开始：

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

如果你使用Lomuto的算法，支点将是最后一个元素，1。这就导致了以下分区的出现：

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

一个理想的枢轴会在less than和greater than的分区之间均匀地分配元素。选择一个已经排序的数组的第一个或最后一个元素作为支点，使得quicksort的性能很像insertion sort，这导致最坏情况下的性能为O(n²)。解决这个问题的一个方法是使用median of three枢纽选择策略。在这里，你找到数组中第一个、中间和最后一个元素的中位数，并将其作为一个支点。这种选择策略可以防止你挑选数组中最高或最低的元素。

让我们来看看一个实现。创建一个名为quicksortMedian.swift的新文件并添加以下函数：

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处，这就是函数的返回值。

接下来，让我们用这个中位数实现一个Quicksort的变体，即三个中位数：

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)
  }
}

这段代码只是quicksortLomuto的一个变体，它首先选择了三个元素的中位数。

通过在你的playground上添加以下内容来尝试一下：

var list3 = [12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 8]
quickSortMedian(&list3, low: 0, high: list3.count - 1)
print(list3)

这一策略是一种改进，但我们能否做得更好？

荷兰国旗的划分¶

Lomuto和Hoare算法的一个问题是，它们不能很好地处理重复的内容。在Lomuto的算法中，重复的内容最终会出现在少的分区中，而不会被归类到一起。用Hoare的算法，情况就更糟糕了，因为重复的东西可能到处都是。

组织重复元素的一个解决方案是使用Dutch national flag partitioning。这种技术是以荷兰国旗命名的，荷兰国旗有三条颜色带：红、白、蓝，类似于你创建三个分区的方式。如果你有很多重复的元素，荷兰国旗分区是一种很好的技术。

让我们来看看它是如何实现的。创建一个名为quicksortDutchFlag.swift的文件并添加以下函数：

public func partitionDutchFlag<T: Comparable>(_ a: inout [T],
                                              low: Int, high: Int,
                                              pivotIndex: Int)
                                              -> (Int, Int) {
  let pivot = a[pivotIndex]
  var smaller = low // 1
  var equal = low // 2
  var larger = high // 3
  while equal <= larger { // 4
    if a[equal] < pivot {
      a.swapAt(smaller, equal)
      smaller += 1
      equal += 1
    } else if a[equal] == pivot {
      equal += 1
    } else {
      a.swapAt(equal, larger)
      larger -= 1
    }
  }
  return (smaller, larger) // 5
}

你将采用与Lomuto分区相同的策略，选择最后一个元素作为pivotIndex。让我们来看看它是如何工作的：

每当你遇到一个小于枢轴的元素，就把它移到smaller的索引。这个规则意味着在这个索引之前的所有元素都小于支点。
索引equal指向下一个要比较的元素。等于中枢的元素被跳过，这意味着在smaller和equal之间的所有元素都等于中枢。
每当你遇到一个大于枢轴的元素，就把它移到索引larger。这条规则意味着所有在这个索引之后的元素都比中枢大。
主循环对元素进行比较，如果需要的话，进行交换。这个过程一直持续到索引equal移过索引larger，意味着所有元素都被移到正确的分区。
该算法返回指数smaller和larger。它们指向中间分区的第一个和最后一个元素。

分解步骤¶

让我们看一个使用unsorted数组的例子：

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

由于该算法与支点选择策略无关，因此采用Lomuto，挑选最后一个元素8。

Note

为了练习，可以尝试不同的策略，如三者的中位数。

接下来，你设置指数smaller、equal和larger：

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

第一个要比较的元素是12。因为它比中枢大，所以它与索引为larger的元素互换，并且这个索引被递减。

注意索引equal没有被增加，所以下一个被交换的元素（8）被比较：

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

记住，你选择的支点仍然是8。8等于支点，所以你增加equal：

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

0比中枢小，所以你把equal和smaller的元素交换，并增加两个指针：

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

以此类推。

注意smaller, equal和larger是如何分割数组的：

[low...<smaller]中的元素比中枢小。
[smaller..<equal]中的元素等于中枢。
[larger>..high]中的元素比中枢大。
[equal...larger]中的元素还没有被比较。

为了了解该算法如何以及何时结束，让我们从倒数第二步继续：

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

这里，27正在被比较。它比中枢大，所以它与1互换，索引larger被减去：

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

尽管equal现在等于larger，但这个算法还没有完成。

目前在equal的元素还没有被比较。它比中枢小，所以它与8互换，指数smaller和等于都被递增：

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

指数smaller和larger现在指向中间分区的第一个和最后一个元素。通过返回它们，该函数标记了三个分区的边界。

现在你已经准备好使用荷兰国旗分区来实现新版本的quicksort：

public func quicksortDutchFlag<T: Comparable>(_ a: inout [T],
                                              low: Int, high: Int) {
  if low < high {
    let (middleFirst, middleLast) =
      partitionDutchFlag(&a, low: low, high: high, pivotIndex: high)
    quicksortDutchFlag(&a, low: low, high: middleFirst - 1)
    quicksortDutchFlag(&a, low: middleLast + 1, high: high)
  }
}

注意递归是如何使用middleFirst和middleLast索引来确定需要递归排序的分区的。因为等于枢轴的元素被分组在一起，它们可以被排除在递归之外。

在你的playground上添加以下内容，试试你的新quicksort：

var list4 = [12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 8]
quicksortDutchFlag(&list4, low: 0, high: list4.count - 1)
print(list4)

就这样吧!

关键点¶

幼稚的分区法在每个过滤函数上都会创建一个新的数组；这是不高效的。所有其他的策略都是就地排序。
Lomuto分区法选择最后一个元素作为枢纽。
Hoare分区法选择第一个元素作为其支点。
理想的支点是将元素平均分配到各个分区。
选择一个不好的支点会导致quicksort在O(n²)内执行。
Median of three通过取第一、中间和最后一个元素的中位数找到支点。
Dutch national flag的分区策略有助于更有效地组织重复的元素。

34.快速排序¶

示例¶

分区策略¶

Lomuto的分区算法¶

循序渐进¶

Hoare分区法¶

分解步骤¶

糟糕的支点选择的影响¶

荷兰国旗的划分¶

分解步骤¶

关键点¶

`Lomuto`的分区算法¶

`Hoare`分区法¶