《算法基础：打开算法之门》一3.5 快速排序

本节书摘来自华章出版社《算法基础：打开算法之门》一书中的第3章，第3.5节，作者 ［美］托马斯 H 科尔曼（Thomas H Cormen），更多章节内容可以访问云栖社区“华章计算机”公众号查看

3.5 快速排序

像归并排序那样，快速排序也使用分治模式（因此也使用递归）。然而，快速排序与归并排序所使用的分治法稍微有点不同。与归并排序相比，存在两个不同之处：
●快速排序按照原址工作。
●快速排序的渐近运行时间介于最坏情况和平均情况之间。尤其是，快速排序的最坏运行时间是Θ（n2），但是它的平均情况下的运行时间要更好一些：Θ（nlgn）。快速排序也有好的常数因子（比归并排序更好一些），并且它通常是实践中的一个好的排序算法。这里是快速排序使用分治法的过程。再一次考虑对书架上的书进行排序的例子。就像归并排序一样，最初我们考虑对位置从1～n的所有书进行排序，接着考虑更一般的情况：49对位置从p～r的书进行排序。1分解：首先选择位置在p～r之间的任意一本书，并称这本书为主元。对书架上的书进行重排以便排序在主元的作者名字之前的所有书籍或者是由同一个作者书写的书籍均放置在主元的左侧，排序在主元的作者名字之后的所有书籍均放置在主元的右侧。在这个例子中，我们在重排从位置9～位置15的所有书籍时，选择最右侧的书籍，即选择由Jack London所写的书籍作为主元：

经过重排后——我们称之为快速排序中的划分——由Flaubert和Dickens所写的书籍，即按照字母排序出现在London之前的，被放置在London所写的书籍的左侧，而其他的书籍，即按照字母排序出现在London之后的书籍，被放置在London所写的书籍的右侧。注意，划分后，被放置在London左侧的书籍是无序的，London右侧的书籍也是无序的。2解决：通过递归地对主元左侧的和右侧的书籍进行排序来求解子问题。也就是说，如果分解步骤将主元移动到位置q(例子中的位置11)，随后就会递归地对从位置p～位置q-1的书籍进行排序，同时递归地对从位置q+1～位置r的书籍进行排序。3合并：什么也不用做！一旦解决步骤递归地排序完成后，我们就完成任务了。为什么呢？所有在主元左侧的书籍（位于位置p～位置q的书籍）要么按照字母顺序均位于主元的前面，要么与主元有相同的作者，且已排好序，而所有在主元右侧的书籍（位于位置q+1～位置r的书籍）按照字母顺序均位于主元的后面，且已排好序。因此，从位置p～位置r的所有元素肯定是已经排好序了！如果将该书架改成数组并且将书籍改成数组元素，依然可以采用快速排序的策略。就像归并排序一样，50当待排序的子数组的元素数目少于两个时，基础情况就会发生。对于快速排序，假定我们调用了程序PARTITION(A,p,r)，而PARTITION(A,p,r)用于划分子数组A［pr］，且返回主元最终应放置的位置索引q。

最初的调用是QUICKSORT(A,1,n)，这与归并排序MERGESORT程序类似。如下是递归如何展开的例子，其中每个子数组的索引p、q和r(其中p≤r)表示如下：

在数组每一位的最底端的值给出了最终要存储在该位置的元素。当你从左向右读入数组时，观察在每个位置处的值，你能看出数组确实是有序的。快速排序的关键是划分数组。就像能在Θ（n）时间归并n个元素一样，我们也能在Θ（n）时间划分n个元素。下面介绍如何将书架上位于位置p～位置r的书籍进行划分。选择集合中最右侧的书籍——在位置r处的书籍——作为主元。任意时刻，每本书将被精确地划分到这四个组的一个组中，且这些组均位于位置p～位置r之间，从左到右依次是：●组L(左侧组):这些书籍的作者名字按照字母排序出现在主元之前或者跟主元的作者名字一致。●组R(右侧组):排在组L之后，这些书籍的作者名字按照字母排序出现在主元之后。●组U(未知组):排在组R之后，这些书籍还没有检查，因此不知道它们的作者名字与主元的作者名字相比，排序如何。●组P(主元):排在组U之后，仅仅一本书，即主元。我们自左向右仔细检查组U中的书籍，将它与主元进行比较，并将它移动到组L中或者组R中，一旦检查到主元位置处，即终止所有操作。与主元进行比较的书籍始终是组U中最左侧的书籍。●如果这个书籍的作者名字按照字母排序位于主元的作者名字之后，那么这本书就成为组R中最右侧的书籍。由于这本书是组U中最左侧的书籍，并且组U紧跟在组R之后，我们仅仅需要将介于组R和组U之间的分割线向右移动一个位置，而无需移动其余任何书籍：

●如果书籍的作者名字按照字母排序在主元的作者名字之前，或者等于主元的作者名字，那么我们就将这本书置为组L中最右侧的书籍。我们将它与组R中最左侧的书籍进行调换，并且将组L和组R之间的分割线向右移动一个位置，将组R和组U之间的分割线向右移动一个位置：

一旦判定到主元位置，我们将它与组R中最左侧的书籍进行调换。在我们这个例子中，我们在本节刚开始时显示了书籍的调整情况。我们将每本书与主元比较一次，当书籍的作者名字位于主元作者名字之前或者是等于主元的作者名字就会产生一次调换。因此，为了对n本书进行划分，我们至多进行n-1次比较（由于无需将主元和它本身比较）并且至多进行n次调换。注意，与归并排序不同，快速排序时我们能对书籍进行划分而无需将所有书籍从书架上取下来。也就是说，我们能对书籍进行原址划分。为了将划分书籍的操作转换成划分一个子数组A［pr］的操作，我们首先选择将A［r］（最右侧的书籍）作为主元。随后自左向右仔细检查子数组，将每个元素与主元进行比较。我们维持用于划分子数组的索引q和u如下：●子数组A［pq-1］对应着组L:每个元素小于或者等于主元。●子数组A［qu-1］对应着组R:每个元素均大于主元。●子数组A［ur-1］对应着组U:我们还不知道它们和主元的大小情况。●元素A［r］对应着组P:该位置上放置着主元。实际上，这一划分就是循环不变式。（我们不再证明。）53在每一步中，我们将组U中最左侧的元素A［u］和主元进行比较。如果A［u］比主元大，那么将u自增一来将组R和组U之前的分割线向右移动一个位置。如果反之，A［u］小于或者等于主元，那么将元素A［q］(组R中的最左侧元素)和A［u］进行调换，且分别将q和u自增一，这相当于将组L和组R之间的分割线以及组R和组U之间的分割线分别向右移动一个位置。PARTITION程序如下。

初始时刻，将q和u均赋值为p，组L(A［pq-1］)和组R(A［qu-1］)最初时均为空，且组U(A［ur-1］)包含除了主元之外的所有元素。在一些实例中，例如A［p］≤A［r］，会出现一个元素需要与它本身进行调换的情况，这个操作实际上对数组没有任何影响。第3步结束时会将主元元素和组R中最左侧的元素进行调换，因此会将主元移动到划分后的数组的正确位置上，并且随后会返回主元所在的新索引位置q。

下面解释PARTITION程序是如何在子数组A［510］上一步一步运行的，该数组是上面快速排序的例子里第一次划分得到的子数组。组U以白色表示，组L以浅阴影色表示，组R以深阴影色表示，组P（即主元）以最深的阴影色表示。下图的第一个序列表示了最初的数组和相应的索引，接下来的五步表示每次经过程序中第2步循环迭代后所得的序列（包括在每次迭代后将u自增1这一步骤），且最后一步得出了最终划分好的数组。

就像划分书籍一样，我们依次将每个元素和主元比较一次，并且每次比较中，我们至多进行一次调换。由于每次比较需花费常量时间，并且每次调换需要花费常量时间，因此对于具有n个元素的子数组进行PARTITION操作所需要的总时间是Θ（n）。那么QUICKSORT程序需要花费多长时间呢？就像归并排序一样，我们称对一个具有n个元素的子数组进行排序需要的时间为T(n)，即一个随着n增加而增长的函数。由PARTITION程序执行的分解操作需要花费Θ（n）时间。但是QUICKSORT所花费的时间依赖于划分操作得到的结果是否均匀。在最坏情况下，划分得到的大小是相当不平衡的。如果除了主元之外的所有元素均小于主元，那么PARTITION的结果是得到除去A［r］这个主元的剩余部分，且QUICKSORT最终会返回存储在变量q中的索引r值。这种情况下，A［q+1r］是空的，且A［pq-1］仅仅比A［pr］少一个元素。对空的子数组进行递归调用需要花费Θ（1）时间（即在第1步中进行调用和判定子数组是否为空时所花费的时间）。对于划分，我们可将Θ（1）并入Θ（n）时间内。但是如果A［pr］有n个元素，那么A［pq-1］有n-1个元素，因此对于A［pq-1］进行递归调用需要花费T(n-1)的时间。因此，我们得到递归式
我们无法利用主方法来计算这一递归式，但是它有解，即T(n)为Θ（n2）。这并不比选择排序更好一些！我们怎么会得到如此不均匀的划分呢？如果每一主元均比所有的其他元素大，那么虽然数组在开始时就已经是有序的了，55但是会得到一个不均匀的划分。如果数组初始时刻为逆序的，那么每次我们也会得到一个不均匀的划分。另一方面，如果每次我们都能得到一个均匀的划分，那么每个子数组将最多有n/2个元素。递归式将和34节最后针对归并排序的递归式一致，
采用同样的解法，T(n)是Θ（nlgn）。当然，如果遇到这种情况，我们是相当幸运的，或者我们也可以将输入数组进行特殊设计以使每次都能得到一个相对均匀的划分。在通常情况下，快速排序介于最好和最坏情况之间。理论分析过于繁琐，此时不一一推导证明，但是如果输入数组的元素随机产生，那么通常而言我们会得到一个相对均匀的划分，即QUICKSORT程序会花费Θ（nlgn）的运行时间。现在大胆设想一下。假定你的最大的敌人给你一个待排序的数组，并且已经知道你总是选择子数组的最后一个元素作为主元，且调整了数组的顺序以便你每次都会得到最坏情况下的划分。你会怎么对付你的敌人呢？这时，你可以首先判定初始数组是否为正序或者逆序，并在这种情况下做一些特殊处理。随后你的敌人可能再次将你的数组设计为每次都得到最坏情况下的划分，而不是偶尔是坏的划分。此时，你就不想对每种可能的坏的划分情况进行检查了。幸运的是，这里有一个更简单的解决方案：不要总是将最后一个元素选作主元。那么前述的可爱的PARTITION程序将不适合这种情况，因为各个组不再如假定的一样。这或许也不是个难题，在运行PARTITION程序之前，将A［r］和A［p…r］中那个被随机选定的元素进行调换即可。现在你已经随机选择了主元且能够继续执行该PARTITION程序。事实上，再稍稍努力，你将更容易得到一个接近均匀划分的情况。我们不再是从A［p…r］中随机选取一个元素作为主元，而是从A［p…r］中随机选取三个元素并将这三个元素的中位数和A［r］调换顺序。这里的中位数是指值介于另外两个元素之间的那个元素。（如果随机选择的元素中有两个或者更多的元素相等，那么我们会再随机地选择元素以消除这种情况。）再者，我不想让你面临这种情况，但是倘若你每次因选择随机元素而使得QUICKSORT花费比Θ（nlgn）更长的时间，你将是相当不幸的。而且，如果待排序的值都不同，那么除非你的敌人已经获取了你的随机数字产生器，否则你的敌人是无法控制你划分结果的均匀程度的。56QUICKSORT需要将元素调换多少次？那依赖于你是否将某元素“调换”至它本身的位置（即原地调整）看作是一次调换。你当然能够检查是否存在这种情况，并且如果存在的话，要避免这一调换。因此当且仅当一个元素确实因调换操作在数组中移动了位置，即PARTITION操作中当第2A步中q≠u或者当第3步中q≠r成立时，才被称作是一次调换。最少化调换次数的最好情况也是QUICKSORT渐近时间的一个最坏情况：当数组已经是有序时，那么没有调换操作发生。调换次数最多时等价于当n为偶数且数组类似于n,n-2,n-4,…,4,2,1,3,5,…,n-3,n-1。那么会产生n2/4次调换，且渐近运行时间也仍然是最坏情况Θ（n2）。