第34章：快速排序

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

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

[ elements < pivot | pivot | elements > pivot ]

在本章中，你将实现quicksort，并研究各种分区策略，以获得这种排序算法的最大效益。

例子

打开启动器的操场。quicksortNaive.swift中提供了quicksort的天真实现。

上面的实现以递归方式将数组过滤成三个部分。让我们来看看它是如何工作的。

数组中必须有一个以上的元素。如果没有，则认为该数组已被排序。
选择数组中的中间元素作为你的支点。
利用支点，将原数组分成三个部分。小于、等于或大于支点的元素进入不同的桶中。
递归排序，然后合并这些分区。

现在让我们把上面的代码可视化。给出下面这个未经排序的数组。

在这个实现中，你的分区策略是总是选择中间的元素作为支点。在本例中，这个元素是8。使用这个支点对数组进行分区的结果是以下分区。

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

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

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

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

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

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

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

分区策略

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

Lomuto的分区

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

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

这个函数需要三个参数。

a是你要分割的数组。
low和high设置你要分割的数组中的范围。这个范围会随着每次递归而变得越来越小。

该函数返回支点的索引。

现在，按如下方式实现该函数。

以下是这段代码的作用。

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

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

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

逐步进行

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

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

首先，选择最后一个元素8作为支点。

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

第二个元素0比中枢小，所以它与目前在索引i（12）的元素互换，并增加i。

第三个元素3又比中枢小，所以又发生了交换。

这些步骤一直持续到除枢轴元素外的所有元素都被比较过。得到的数组是。

最后，支点元素与当前索引i处的元素互换。

Lomuto的分区现在已经完成。注意支点是如何在小于或等于支点的元素和大于支点的元素这两个区域之间的。

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

有了你的分区算法，你现在可以实现quicksort了。

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

你可以通过在你的操场上添加以下内容来尝试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的分区算法总是选择第一个元素作为支点。让我们看看这在代码中是如何工作的。

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

让我们来看看这些步骤。

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

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

循序渐进

给出下面这个未经排序的数组。

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

首先，12被设定为支点。然后，i和j将开始在数组中运行，寻找不小于（对i而言）或大于（对j而言）中枢的元素，i将停在12元素处，j将停在8元素处。

然后这些元素被调换。

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

然后进行互换。

接下来，18和8被互换，接着是27和5。

这次交换后，数组和索引如下。

下次你移动i和j时，它们会重叠在一起。

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

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

通过在你的操场上添加以下内容来试试。

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]

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

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

这里，你通过排序找到a[low]、a[center]和a[high]的中位数。中位数最终会出现在索引中心，这就是函数的返回值。

接下来，让我们用这个中位数实现一个变种的Quicksort。

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

通过在你的操场上添加以下内容来尝试一下。

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的算法中，情况甚至更糟，因为重复的元素可能到处都是。

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

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

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

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

循序渐进

我们来看看下面这个未排序数组的例子。

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

因为这个算法与支点选择策略无关，所以采用Lomuto，挑选最后一个元素8。

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

接下来，你设置了较小、相等和较大的指数。

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

需要注意的是，索引相等的元素不会被递增，所以在(8)中被交换的元素接下来被比较。

记住，你选择的中枢仍然是8。8等于支点，所以你的增量等于。

0比中枢小，所以你把相等和较小的元素互换，增加两个指针。

以此类推。

注意较小、相等和较大是如何划分数组的。

在[low...<smaller]中的元素比中心点小。
在[smaller...<equal]中的元素等于支点。
在[大>...高]中的元素比支点大。
在[等于...大]中的元素还没有被比较。

为了了解该算法如何以及何时结束，让我们从第二至最后一步继续。

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

尽管equal现在等于large，但算法并没有完成。

目前处于相等位置的元素还没有被比较。它比枢轴小，所以它与8互换，小的和等于的指数都被递增。

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

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

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

在你的操场上添加以下内容，试试你的新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²)中执行。
三者的中位数通过取第一、中间和最后一个元素的中位数找到支点。
荷兰国旗的分区策略有助于更有效地组织重复的元素。

上一章	目录	下一章