数据结构（邓俊辉）学习笔记】排序 2——快速排序：性能分析

1. 不稳定 + 就地

以下针对刚才所给出的快速排序算法的第一个版本，就其性能做一分析。

首先很遗憾地发现，这个算法是不稳定的。快速排序算法的不稳定性通过我们刚才所举的那个实例可以清楚地看出来。

注意到，在原始的输入序列中有两个5，按照先后次序，我们分别用5A 和5B 来表示。

在经过一次划分之后，我们可以看到这两个元素的位置已经彼此颠倒。实际上这种现象必然是普遍存在的。因为对于任何两个小于候选轴点的元素而言，它们加入子序列 L 的次序必然是颠倒的。同理对于大于候选轴点的雷同元素而言，也有对称的性质。

其次整个算法也是可以就地实现的，也就是说它只需要常数的附加空间。这一点从刚才这组原理和过程图中也可以清晰地看出。

实际上除了原始的输入序列，我们这里只需要维护常数个指针以及用于保存候选轴点的一个单元。

2. 最好情况 + 最坏情况

那么整个算法的运行时间呢？我们知道，对于归并排序而言，整个算法的运行时间可以保证不超过 n*log n。我们也知道其关键在于归并排序可以保证任何一对被划分出来的子任务在规模上都是彼此相当的，也就是规模都接近二分之N。因此总体的运行时间也就是求解两个这样的问题，再加上为了将它们的结果合并所需要的线性时间。

很遗憾，快速排序算法却不能像归并排序算法那样保证子任务划分时的均衡性。实际上partition 算法的每次划分结果与其说是取决于这个算法，不如说取决于最初选定的候选轴点。

如果候选轴点在最终有序列中所对应的秩为 r，那么经划分之后所得到的序列 L 的长度也必然就是 r。而对应的子序列 G 的长度也必然为 n 减 1 再减 r。划分的结果是否均衡完全取决于我们的运气。

• 在最好的情况下，我们的每次划分都是均衡的，或者至少是接近均衡的，于是我们自然可以达到最优的 n*logn。

• 然而反过来，在最坏的情况下，有可能我们的每一次划分都不均衡，甚至极不均衡。比如最为极端的一种情况就是，每一个候选节点都是在当前而言最小或者最大的极值元素，以至于在划分之后，子序列 L 为空或者 G 为空。也就是说，在我们所划分出来的一对子任务中，总是有一个规模为零，而另一个相对于此前的规模只减少了一个单位。

  根据这个递推式不难解出，此时算法所需要的总体运行时间必然是平方量级的。也就说与起泡排序等低级算法居然性能是相当的。

当然采用一些简明的策略，在付出足够小的代价之后，我们的确可以在一定程度上降低最坏情况出现的概率。比如我们可以采用所谓随机选取法，也就说不再是每次都固定地将首元素作为候选轴点。而是在整个序列中，随机地选择其一。另一种更为有效的方法是所谓的三者取中法，也就是说我们每次都是在整个序列中随机地抽取3个元素，然后将其中数值居中的那个作为候选轴点。

当然，无论采用什么方法，我们也只能是在一定程度上降低最坏情况出现的概率，而无法根本的杜绝最坏情况的出现。既然如此，我们接下来不得不回答的一个问题就是，就基本的快速排序算法而言，其平均性能又有多高呢？

3.平均情况

非常幸运的是，以上基本的快速排序算法在常规的随机意义下，平均性能的确可以达到最优的 n log n。

以下我们不妨针对最为常见的均匀独立分布来做一精确的估算，也就说我们在这里假设，所有的元素都是均匀的取自于某一个数值范围。同时各元素在确定各自取值时是互不依赖的。

我们来考察任何一个这样的随机序列，调用 partition 算法对它进行的划分将有几种可能呢？无非 n 种可能，具体的哪种情况完全取决于最初所选定的那个候选轴点。

更准确地讲，是这个候选轴点在最终有序列中所具有的秩。如果将候选轴点的这个秩记作 k，那么 partition 算法所输出的子序列 L 长度也应该是 k，这个子序列所对应的那个子任务所需的平均运行时间也因此就可以表示为Tk。对称的 partition 算法所输出的子序列 G 长度应该为 n 减 k 减1，这个子序列所对应的那个子任务从递归的角度来看，所需要的平均运行时间也因此可以表示为 T n 减 k 再减1。这样的一对排序子任务总共所需要的运行时间也自然就是二者之和。

进一步的，既然按照假设这里服从均匀独立分布，因此各种情况出现的概率应该均等。具体来说都是 n 分之1。因此所有这些情况所对应的平均运行时间，也就是用这个概率对它们的总和进行平均。以下的分析，焦点就会聚在这个求和号上。尽管这个求和涉及到前后两个序列，但是略加观察之后，我们不难发现，这两个序列的求和应该完全是相等的，你能看出原因来吗？

没错，这两个序列的取值范围都是从 0 到 n 减1 ，只不过前者是递增的，从0到 n 减1，而后者只不过是递减的，从 n 减1到0。因此我们只需保留其中的一项，同时作为补偿将它的系数加倍。

接下来我们将这个等式的两端同时乘以 n，于是就可以得到这样一个等式。如果将其中所有的 n 都替换为 n 减1，我们又可以进而得到下面这个等式。现在我们只需将这两个等式相减，就可以得到这样一个等式。除了系数，这个等式主要都包含一个 Tn 以及两个 T n 减一。

接下来我们只需对 Tn 和 Tn 减1合并同类项，就可以得到这样一个等式。对于这样一个等式，我们不妨令它的左右两端同时除以 n 以及 n 加1。

于是就可以得到这样一个等式，如果我们将这个等式的左侧表示和理解为另一个函数 Sn，那么右侧的这一项也就对应于 Sn 减1。这样我们也得到了一个关于 Sn 的简明递推式。

因此接下来，我们可以进而将右侧的 Sn 减 1 替换为 Sn 减2。当然，为此我们需要追加一项，这种地推可以持续进行下去，也就说我们可以将 Sn 减2替换为 Sn 减3，再将 Sn 减3替换为 Sn 减4以及 Sn 减4替换成 Sn 减5，诸如此类。

在递推到最终一步之前，我们所引入的各项将构成一个级数。你应该看得出来这是一个什么级数。没错，调和级数。我们在第一章就曾介绍过，就渐进意义而言，调和级数是与自然对数 log n 同阶的。

由此可见，我们这里所需要估计的快速排序算法的平均运行时间在渐进意义下的确不超过 n * log n，那么它对应的常系数呢？为此，我们只需将 log n 替换为以2为底的对数，相应的也自然可以得知常系数应为两倍的 ln2，具体来说也就大致为1.39。

这样小的一个长系数，也保证了快速排序算法在通常情况下的优异性能，也就是说，快速排序的确名符其实。