1.5　实例：快速排序算法的分析

为了说明被忽略的基本算法，我们研究下一个相当重要的特殊算法——快速排序算法。该算法是在1962年由C.A.R. Hoare提出的，他的论文[15]是算法分析中较早而且十分出色的典范。Sedgewick[27]（也可见参考资料[29]）也将快速排序算法的分析论述得很详细，我们在此仅针对其重点进行阐释。详细研究这种分析是值得的，不仅是因为该排序方法使用广泛，其分析结果直接与实践相关，也是因为分析本身就能说明许多问题，这些问题我们将会在本书的后面遇到。特别的是，相同的分析也适用于树结构基本性质的研究，这种结构具有广泛的价值和适用性。更一般地说，对快速排序算法的分析表明了我们如何分析一种广泛的递归程序。

程序1.2是快速排序算法在Java中的实现。这是一个递归程序，通过将数组分成两个独立（较小）的部分，然后将这两部分分别排序，从而实现对整个数组的排序。显然，当遇到空的子序列时，递归终止，而我们设计的算法实现也会将大小是1的子序列作为停止点。

程序1.2　快速排序算法

这个细节似乎无关紧要，但正如我们将看到的那样，递归的本质就是确保程序将被用于大量的小分支，而这种简单的改进可以显著提升性能。

划分过程把位于数组最后位置上的元素（分隔元，partitioning element）放入正确的位置，使其之前的元素都比它小，之后的元素都比它大。该程序使用两个指针来实现划分：一个指针从左边扫描数组，另一个指针从右边扫描数组。左指针递增，直至找到大于分隔元的元素；右指针递减，直至找到小于分隔元的元素。然后把两个元素交换，并且该过程继续，直至指针相交，此时的位置就是分隔元的放置位置。确定位置后，程序用a[hi]替换a[i]，把分隔元放入指定位置。最后调用quicksort(a,0,N-1)完成数组排序。

有几种方法能实现刚刚概述的一般递归策略；上面描述的实现方法取自参考资料[30]（也可见参考资料[27]）。以分析为目的，我们假设数组a包含随机排序的不同数值，但请注意，此代码对于所有输入（包括相等的数字）都能正常工作。也可以在更切合实际的模型下研究这个程序，即允许相等的数值（见参考资料[28]）、长字符串关键字（见参考资料[4]）以及许多其他情况。

一旦实现了算法，分析的第一步就是估计这个程序各个指令的资源需求。这取决于特定计算机的性能，所以我们忽略这些细节。例如，“内层循环”指令：

在一般计算机上可能会将其转换为汇编语言指令，如下所示。

该循环的每次迭代可能需要4个单位时间（每个内存引用一个）。在现代计算机上，由于缓存、管道以及其他影响，准确地估计开销变得更为复杂。内循环中的另一个指令（递减j）与上面的指令（递加i）是相似的，但是需要额外检验判断j是否超出边界。但如果使用警戒标记，就无须进行额外检验，所以我们可以忽略其多余的复杂性。

分析的下一步是将变量名分配给程序中指令的执行频率。正常情况下只涉及少数真变量：所有指令的执行频率都可以用这些变量表示。此外，我们希望将这些变量与算法本身相关联，而不是任何特定程序。快速排序算法涉及3个自然量：

A——分隔阶段数；

B——交换次数；

C——比较次数。

在一般计算机上，快速排序算法的总运行时间可以用公式表示，即

　　（2）

这些系数的精确值取决于编译器生成的机器语言程序和所使用的计算机的属性；上面给出的是典型值。比较在同一计算机中实现的不同算法时，这个表达式是很有用的。事实上，即使Mergesort是“最优”算法，Quicksort仍具有重要的实际意义，其原因在于：Quicksort每次比较的开销（C的有效性）可能明显低于Mergesort的开销，进而导致在一般实际应用中Quicksort的运行时间明显缩短。

定理1.3（Quicksort分析）　对N个顺序随机且元素互异的数组排序，Quicksort平均使用

个分隔阶段，

次比较，

次交换。

证明：在这里，准确的答案用调和级数

表示，这是我们在算法分析中将会遇到的许多著名“特殊”数列中的第一个。

与Mergesort一样，Quicksort的分析涉及定义和求解直接反映算法递归性质的递归关系。但在这种情况下，递归必须基于关于输入的概率表述。如果CN是排列N个元素的平均比较次数，则且

　　（3）

为了得到总的平均比较次数，我们把第一次分隔阶段的比较次数（）加到用于分隔后的子序列的比较次数中。当分隔元是第j个最大元素（对于每个，其出现的概率是1/N）时，分隔后的子序列大小分别为 和 。

现在，分析被简化为数学问题式（3），它已经不依赖于程序或算法的性质了。这种递归关系比公式（1）稍微复杂一些，因为公式的右边直接取决于前面所有的值，而且这些值不止几个。尽管如此，求解式（3）也并不困难：首先在和的第二部分中把j变为，得到

然后乘以N，减去当数组元素个数为时的同一个公式，消除求和项后得到

再重新排列各项，得到一个简单的递归

两边同时除以，得

重复代入，最后剩下

这就完成了证明，因为。

如上所述，每个元素都用于一次分隔，因此阶段总数为N；先计算第一次分隔阶段的平均交换次数，就可以从这些结果中得到平均交换次数。

该定理所述的近似值由著名的调和级数近似值得到。我们将在第4章仔细研究这种近似。

习题1.12　给出Quicksort对N个元素的N！种全部排列所用比较总次数的递归。

习题 1.13　证明分隔随机排列之后得到的子序列本身都是随机排列。然后证明，如果分隔时右指针初始化为j:=r+1，那么情况会有所不同。

习题1.14　按照上面的步骤求解递归

习题1.15　证明第一次分隔阶段（在指针交叉之前）用的平均交换次数是(N-2)/6。（因此，根据递归的线性性质，。）

通过生成随机输入数据到程序并计算所用比较次数可得到经验数据，图1.1显示了分析结果与这些经验数据的比较。每次实验用灰色点描述经验结果（图中显示的每个N值对应100次实验），黑色点表示N的平均值。分析结果是一条平滑曲线，它拟合了定理1.3给出的公式。正如预期的那样，曲线拟合得非常好。

图1.1　Quicksort所需比较次数：经验结果和分析结果

例如，定理1.3和公式（2）说明，在前面描述的特定机器上，对一个N元素的随机序列进行排序，Quicksort大约需要11.667NlnN-0.601N个步骤；而对于其他机器，也可以像公式（2）和定理1.3讨论的那样，通过考查机器的性质推导出类似的公式。这种公式可用于（非常准确地）预测Quicksort在特定机器上的运行时间。更重要的是，它们可用于估计和比较算法的变量，并为其效果提供量化证据。

因为适当关注细节能够排除机器依赖性，所以本书中我们通常专注于分析与一般算法相关的量，例如“比较”和“交换”。这不仅使我们集中精力于分析的主要技巧，还可以扩展结果的适用性。例如，排序问题的一个较广泛的特点是：将待排序元素视为除排序关键字（key）之外的其他信息的记录（record）。因此访问一个记录（取决于记录的大小）可能比进行一次比较（取决于记录和关键字的相对大小）的开销更昂贵。然后，我们从定理1.3得知，Quicksort比较关键字约2NlnN次，移动记录约0.0667NlnN次，并且我们能更加精确地估计开销或在适当的时候与其他算法进行比较。

Quicksort可以通过多种方式改进自身，成为在许多计算环境下被优先选择的排序方法。我们甚至可以分析复杂的改进版本，并得出平均运行时间的表达式[29]，而且该表达式紧密地匹配所观察到的经验数据。当然，提出的改进方法越复杂，分析也就越复杂。可以通过扩展以上给出的论证来处理某些改进，但是另一些改进则需要更强有力的分析工具。

小型子序列

Quicksort最简单的变体是基于下面的观察结果：对于非常小的序列，Quicksort不是非常有效（例如，如果对大小为2的序列进行排序，只需一次比较，可能还要一次交换），所以比较小的序列应该用更简单的排序方法。下面的习题说明了如何通过扩展以上分析结果来研究一种混合算法，其中“插入排序”（见7.6节）用于长度小于M的序列。那么，这种分析方法有助于选择参数M的最优值。

习题1.16　当用Quicksort对一个大小为N的随机序列进行排序时，平均能遇到多少长度小于或等于2的子序列？

习题1.17　如果我们把前面实现快速排序算法程序的第一行改为

那么排序N个元素所需的总比较次数可由下面的递归关系描述

根据定理1.3中的证明方法准确解出该递归关系。

习题1.18　忽略习题1.17的答案中的较小项（明显小于N的项），求函数f(M)，使比较次数近似于

画出函数f(M)，并找出将该函数最小化的M值。

习题1.19　当M变大时，比较次数从刚刚推导的最小值增加。M增加到多大时，才能使比较次数超过原来（当M=0时）的次数？

三数中值Quicksort

Quicksort的自然改进就是使用如下抽样：选取小样本，然后将样本的中值作为分隔元，这样估计的分隔元更可能接近于序列的中值。例如，如果我们把3个元素作为一个样本，那么这种“三数中值”Quicksort所需的平均比较次数可由下面的递归关系描述

　　（4）

其中是二项式系数，表示从N项中选取3项的选取方法的数量。因为第k个最小元素是分隔元的概率为（与正常Quicksort的1/N相反），所以上面的公式成立。我们希望能够求解这种性质的递归关系，以便确定需要使用多大的样本以及何时切换到插入排序。然而，求解这种递归关系需要使用的技巧比迄今为止所涉及的技巧都要复杂。在第2章和第3章，我们将学习准确求解这种递归的方法，这些方法能够确定参数的最佳值，例如样本大小和小型子序列的分割。根据这些方面的广泛研究得出结论：对于一般实现方法而言，三数中值Quicksort运用从10到20范围内的截止点，使实现接近最佳性能。

基数—交换排序

Quicksort的另一种变体利用了下面这一事实：关键字可以被视为二进制字符串。我们分隔序列不是通过比较序列中的关键字，而是通过把所有前导位是0的关键字都置于所有前导位是1的关键字之前。然后，将得到的子序列用第二位以相同的方式进行独立地分隔，以此类推。Quicksort的这种变体叫作“基数—交换排序”或“基数Quicksort排序”。那么这种变体与基本算法如何比较呢？为了回答这个问题，首先我们必须注意：因为由随机位组成的关键字与随机排列有本质上的区别，所以需要用到不同的数学模型。“随机位串”模型可能更加切合实际，因为它反映了实际的表示法，但可以证明这两个模型大致上是等价的。在第8章我们将更加详细地讨论这个问题。通过类似上面给出的证明方法，可以证明：这种方法所需的位平均比较次数可由下面的递归关系描述

事实证明，这个递归关系比前面给出的递归关系更难求解——在第3章，我们将看到母函数把这个递归关系转换为CN的明确数学公式；在第4章和第8章，我们将学习如何得到一个近似解。

这种分析方法在适用性上有局限性——上述所有递归关系均取决于算法的“保持随机性”性质：如果原序列是随机排序的，那么可以证明，分隔后的子序列也是随机排序的。算法的实现没有这样的限制，而且算法广泛使用的许多变体也不符合该性质。这种变体似乎非常不利于分析。幸运的是（从分析学家的角度来看），经验研究表明，这种变体的性能也同样不佳。因此，虽然没有进行分析量化，但保持随机性的要求似乎有助于设计出更精致、更有效的Quicksort实现方法。更重要的是，如前所述，保持随机性的算法确实得到了性能上的改进，而且这些改进完全可以从数学上量化。

数学分析在Quicksort实际变体的研究中发挥着重要作用。而且我们将看到，还有许多其他问题需要考虑，其中详细的数学分析是算法设计过程的重要组成部分。