vlambda博客
学习文章列表

大家好，我是梁唐。

今天我们继续来看《算法第四版》一书，在上一篇文章当中我们介绍了快速排序的原理，并且也用Python和C++对于快排的两种实现方式进行了实现。

但有一个问题没有讨论，就是快排的性能问题。

之前我们默认采用的是选择最后一个元素作为划分数组的依据，当然这个也可以随意调节，也可以按照自己喜欢选择中间的元素或者是开头的元素。但不管怎么选，都有一个问题避免不了：出现极端情况怎么办？

比如我们选了数组中最小或者最大的元素作为依据，这样一来，我们划分之后，有一边的长度为0，我们期望中的分治的情况没有出现，数组的规模没有明显的减小。

只是一次划分不均衡倒还好，但如果每一次都出现这样的极端情况，会出现什么结果？很明显，会导致我们的算法复杂度过高。简单分析一下，极端情况下，我们每次划分数组，数组的长度只会减少1。对于长度为n的数组来说，需要执行n次划分才能完成排序。每一次划分的复杂度是 ，所以总体上复杂度会蜕化到 ，这也是为什么算法书中会说快速排序的复杂度上限是 的原因。

这显然是我们不愿意看到的，所以我们需要针对这种情况进行优化。

关于这一点的优化其实有很多种方法，我们今天来一一介绍。

乱序法

这是《算法》一书当中提供的方法。

这种方法简单粗暴，既然只有在逆序的情况下会出现复杂度蜕化成 的极端情况，那么我们只要保证这种情况不会出现，或者是几乎不会出现即可。

怎么保证呢？

《算法》书中给出的答案是乱序，反正最终排序结束之后的结果是一样的。既然如此，索性在排序之前先进行打乱。通过简单的数学证明可以知道，对于一个长度为n的数组来说，一共有 种排列。乱序之后刚好是逆序的可能性是 ，对于较大的n来说，刚好出现逆序的几率几乎为0，就避免了算法复杂度蜕化的发生。

乱序我们可以使用洗牌算法，即遍历每一张牌，随机将它和它之后的任意一张牌进行交换。

void shuffle(vector<int>& nums) {
  int n = nums.size();
   for (int i = 0; i < n; i++) {
       // 从 [i, n-1] 中随机出一个位置
       int p = rand() % (n-1-i) + i;
       swap(nums[p], nums[i]);
    }
}

显然，洗牌算法是一个 的算法，我们只需要在排序之前对整个数组进行一次乱序即可，对于总体的复杂度来说不会产生影响。

三点中值法

这个方法在书中也有提到，并且它也是C++ STL中sort函数所使用的方法。

三点中值法的原理也非常简单，我们可以分别选出数组头尾和中间三个元素，然后再求这三个元素的中值作为划分数组的pivot。

这个做法很好理解， 相信也不用我过多解释了。

BFPRT算法

最后介绍的这个方法实在是重量级，首先可以发现它的名字很奇怪，不像是一个正常的英文单词，这是因为它是由Blum、Floyd、Pratt、Rivest、Tarjan五位大牛一起发明的，所以用了他们名字的第一个字母组成了算法的名字。

如果你看过算法导论，那么这五位大佬对你来说想必不会太陌生，几乎都能在其他算法当中找到他们的身影。

吐槽一下，老外在起名字这件事上是非常落后的，总是拿人名凑数，完全不表意。所以五个人名联合作为算法名也就见怪不怪了……

算法的流程很简单，一共只有几个步骤：

1. 判断数组元素是否大于5，如果小于5，对它进行排序，并返回数组的中位数
2. 如果元素大于5个，对数组进行分组，每5个元素分成一组，允许最后一个分组元素不足5个。
3. 对于每个分组，对它进行插入排序
4. 选择出每个分组排序之后的中位数，组成新的数组
5. 重复以上操作

我在之前的文章当中曾经详细介绍过这个算法，也证明过它的复杂度。如果不要求那么严谨，我们也可以拍脑袋大概感知一下。每次迭代之后需要遍历的元素数量变成之前的五分之一，通过等比数列求和可以知道，总共遍历的元素数量小于2n，所以这也是一个 的算法。

由于我们取的是中位数的中位数，假设我们最终选出的数是x。那么在这n/5个分组当中，有一半的中位数小于x，还有一半大于x。在中位数大于它的分组当中至少有3个元素大于等于它，所以整体而言，至少有 n/10 * 3 = 0.3n的元素大于等于x，同理也可以证明有30%元素小于等于x。所以最坏的情况选出来的x是70%位置的数，虽然不能保证严格均等，但保证了最坏的情况足够好。

最后贴一下算法的实现，这里我用了Python，更加接近伪代码：

def bfprt(arr, l=None, r=None):
    if l is None or r is None:
        l, r = 0, len(arr)
    length = r - l
    # 如果长度小于5，直接返回中位数
    if length <= 5:
        arr[l: r] = insert_sort(arr[l: r])
        return l + length // 2
    medium_num = l
    start = l
    # 否则每5个数分组
    while start + 5 < r:
        # 对每5个数进行插入排序
        arr[start: start + 5] = insert_sort(arr[start: start + 5])
        # 将中位数交换到medium_num位置，保证连续
        arr[medium_num], arr[start + 2] = arr[start + 2], arr[medium_num]
        medium_num += 1
        start += 5
    # 特殊处理最后不足5个的情况
    if start < r:
        arr[start:r] = insert_sort(arr[start:r])
        _l = r - start
        arr[medium_num], arr[start + _l // 2] = arr[start + _l // 2], arr[medium_num]
        medium_num += 1
    # 递归调用，对中位数继续求中位数
    return bfprt(arr, l, medium_num)

虽然BFPRT算法牛叉哄哄，但大多数情况下我们对于元素的排列没有这么高的要求。只是使用简单的乱序法或者是三点中值法也可以达到类似的效果，BFPRT算法带来的性能优势太小了，导致了它使用范围并不大，并且知名度也不高，甚至在很多算法书上都找不到相关的介绍，不得不说有些对不起这五位大佬。

好了，关于快速排序的复杂度分析以及优化方案，就聊到这里，感谢大家的阅读。