拜托，面试官别问我「快速排序」了

迈不过友情╰ 2023-07-10 08:13 113阅读 0赞

点击上方蓝字设为星标![format_png][]

下面开始今天的学习～

![format_png 1][]

作者 | 梁唐

来源 | TechFlow

今天我们一起来看一个可以更快实现选择的**快速选择算法**。

## 思维推导 ##

在公布答案之前，我想先带着大家试着推导一下解法。

这其实才是算法能力的精髓，即是应用已知能力解决未知问题的能力。

我们学的各种各样的算法都可以看成是已知能力，已知能力越多，说明能力的边界越广，也就意味着理论上可以解决的问题也就越多。

相比已知能力，解决问题的能力同样重要，尤其是当我们有了一定的基础之后，这一点甚至更加重要。因为有了这项能力，在一些极端情况下我们甚至可以自己推导出新算法，也即是开创和创新。

假设当下我们并不知道正确的解法是什么，我们想要尽可能快地找到前K大的元素。

如果一个一个找这个过程会很慢，除非我们可以做到的查找。显然这是不可能的，因为即使是平衡树这类快速查找的数据结构，单次查找也需要。所以一个一个找是不行的。那么就只剩下一批一批找，批量查找又有两种，一种是直接查找K个，还有一种是多次查找，最后得到正解。

我们并不知道哪种方法更靠谱，但是第一种看起来不太可行，因为它就是问题本身，第二种方法看起来稍微可行一些。在这个问题下，我们并没有多余的信息，想要直接查找K个元素应该不太容易。所以可能通过多次查找得到解是比较好的方法。

多次查找也可以简单分为两种情况，一种是每次查找一批，最后合并在一起，还有一种是每次缩小查找的范围，最后锁定答案。

到这里，如果你对分治算法熟悉的话，你会觉得它和分治算法的应用场景很相似。我们想要求解一个比较大的问题，但是直接求解很困难，所以我们将它拆解，**将大问题拆解成小问题，通过对小问题的解决来搞定原本的大问题**。

我们目前比较熟悉的分治算法好像只有归并排序和快速排序这两个，我们可以试着把这两个算法往这个问题上套。

归并排序核心思路是每次将数组一分为二，然后通过这两个数组归并的过程找到我们想要的解法。这个方案可行，但是和排序并没有区别。

我们文章开头就已经说过了，我们想要寻找的是比排序更快的算法。再看快排，它每次是设置一个标杆，然后对数组当中的元素进行调整，保证比标杆小的元素都在它的左边，比它大的都在它的右边。

标杆最后在的位置就是数据有序之后它正确的位置。**这个方法好像和我们想要的很接近。**

于是，我们就这样顺藤摸瓜，找到了正确的方法。当然实际的思考过程可能要比这个复杂，考虑的情况也会更多，但是总体的思维推导过程应该是差不多的。同样是解题，新手往往靠灵光一闪，而高手都是有一个完整的思维链。

很多算法问题看起来一头雾水，但其实是有迹可循的。**训练出一个思维模型**来寻找正确的解法是新手通往高手的必经之路，也是算法能力的核心。

## 算法原理 ##

我们来仔细分析一下，一次快速排序的调整之后，我们可以确定标杆的位置，这样一来就有三种情况。第一种，它所在的位置刚好是K，说明它前面的这一段数组就是答案，直接返回即可。如果它小于K，说明这个标杆取小了，我们应该在它右侧的数组当中重新选择一个标杆。如果它大于K说明这个标杆取大了，我们可以直接忽略它右侧的元素，因为它右侧的元素一定不在答案里。

我们可以参考一下下面这张图：

![format_png 2][]

思路有了，代码就不难写了：

def quick_select_without_optimizer(arr, k):
        n = len(arr)
        # 如果k大于n，没啥好说的，直接返回
        if k >= n:
            return arr
    
        # 缓存
        buffer = []
        while arr:
            # 选择最后一个元素作为标杆
            mark = arr.pop()
            less, greater = [], []
            # 遍历数组，将元素分为less和greater
            for x in arr:
                if x <= mark:
                    less.append(x)
                else:
                    greater.append(x)
            # 判断三种情况，如果相等直接返回
            if len(less) == k:
                return less
            # 如果小于，将less存入buffer，因为它一定是答案的一部分，可以简化计算
            elif len(less) < k:
                buffer += less
                # k要减去less的长度
                k -= len(less)
                arr = [mark] + greater
            else:
                # 如果大于，直接舍弃右边
                arr = less

## 复杂度分析 ##

写完了代码，我们来分析一下算法的复杂度。有些同学可能会有些疑惑，这个算法和快排基本上一样，为什么会更快呢？

这是因为我们每次迭代的过程中，数组都会被**舍弃一部分**，我们把完整的搜索树画出来大概是下面这个样子。

![format_png 3][]

可以看到，虽然总的迭代次数还是次，但是每一层当中遍历的元素个数不再是n。我们假设每次迭代数组的长度都会**折损一半**，到数组长度等于1的时候结束。我们把每一层遍历的长度全部相加，就得到了一个等比数列：

这个等比数列的长度是，我们套用等比数列求和公式：

也就是说虽然它的形式看起来和快排很接近，但是由于我们在遍历的过程当中，每次都会缩小遍历的范围，所以整体的复杂度控制在了。

当然这也只是理想情况下的复杂度，一般情况下随着数据分布的不同，实际的复杂度也会稍有浮动。可以理解成乘上了一个浮动的常数。

之前我们分析快排的时候曾经得出过结论，如果原始数组是**逆序**的，那么快排的复杂度会**退化**到。

我们当前的快速选择算法和快排算法几乎如出一辙，整个的思路是一样的，也就是说，在数组是逆序的情况下同样会遇到**复杂度升级**的问题。不过好在这个问题并不是不可解的，我们下面就来分析一下关于这种情况的优化。

## 优化探索 ##

优化目标很明显，就是极端情况下复杂度会出现升级的情况。问题出现的原因也已经知道了，是由于**数组逆序**，并且我们默认选择最后一个元素作为标杆。

所以想要解决这个问题的入手点就有两个，一个是数组逆序的情况，一个是标杆的选择。

相比于标杆的选择来说，数组逆序情况的判断不太可取。因为对于不是严格逆序的数组，也一样可能出现复杂度很大的情况。如果我们通过逆序数来判断数组的逆序程度，又会带来额外的开销，所以只能从标杆的选择入手。之前我们默认选择最后一个元素，其实这并**不是标杆选择位置的问题**，因为无论选择什么样的位置，都有可能出现对应的极端情况使得复杂度升级，所以简单地改变选择的位置是不能解决问题的，我们需要针对这个问题单独设计算法。

一个比较简单的思路是我们可以选择首尾和中间三个位置的元素，然后选择其中第二大的元素作为标杆。这种方案实现简单，效果也不错，但是分析一下的话，其实没有从根本上解决问题，因为依然还是可能出现极端情况，比如首尾和中间刚好是三个最大的元素。

虽然这个概率比单个元素出现最大降低了很多。还有一个问题是，这样选出来的标杆**不能保证分割出来的数组是平衡的**。

## BFPRT算法 ##

这里要给大家介绍一个牛哄哄的算法，说它牛不是因为它很难，而是因为它真的很牛。

它的名字叫BFPRT，是由**Blum、Floyd、Pratt、Rivest、Tarjan**五位大牛一起发明的。如果你读过《算法导论》的话，一定会找到其中好几个人的名字。该算法可以找到一个比较合适的标杆，用来在快排和快速选择的时候切分数组。

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

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

算法思路很朴素，其实就是一个**不断选择中位数**的过程。

我们先来证明它的正确性，我们假设最终选出来的数是x，一个长度为n的数组会产生n/5个分组。由于我们取的是中位数的中位数，所以在这n/5个分组当中，有一半的中位数小于x，还有一半大于x。在中位数大于它的分组当中至少有3个元素大于等于它，所以整体而言，至少有 n/10 \* 3 = 0.3n的元素大于等于x，同理也可以证明有30%元素小于等于x。所以**最坏的情况选出来的x是70%位置的数。**

最后，我们来分析一下它的复杂度，我们可以得到一个不等式：

其中是寻找个中位数的复杂度，是递归的最坏的情况，即只能减少30%数组的长度。是我们使用插入排序进行多次排序的复杂度，这里的c是一个常数。

我们很容易可以证明和都是的复杂度，这里我们证明一下前者作为一个例子：

我们把这个式子累加起来，可以得到：

同理，我们也可以证明也是的算法，所以也是的算法。

根据BFPRT算法的定义很容易写出代码：

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])
            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)

这个代码写出来了之后，剩下的就容易了，改动量并不大，只需要加上两行即可。：

def quick_select(arr, k):
        n = len(arr)
        if k >= n:
            return arr
    
        # 获取标杆的下标
        mark = bfprt(arr)
        arr[mark], arr[-1] = arr[-1], arr[mark]
        buffer = []
    
        while arr:
            mark = arr.pop()
            less, greater = [], []
            for x in arr:
                if x <= mark:
                    less.append(x)
                else:
                    greater.append(x)
            if len(less) == k:
                return buffer + less
            elif len(less) < k:
                k -= len(less)
                buffer += less
                arr = [mark] + greater
            else:
                arr = less

看代码的话和上面基本上没有什么差别，唯一的不同就是选择之前先获取了一下标杆。在这里我只是在一开始的时候调用了一次，当然也可以在while循环里每一次都调用，不过我个人觉得没什么必要，因为在获取标杆的时候，会将数组全部打乱，足够避免极端情况了。

今天的文章篇幅有点长，但内容还可以，尤其是 **BFPRT算法**，真的是非常经典，算得上是不复杂但是很巧妙了。

感兴趣的同学可以了解一下它背后五个大佬的故事，估计比我的文章精彩得多。

好了，今天的文章就是这些，如果觉得有所收获，请顺手点个**在看或者转发**吧，你们的举手之劳对我来说很重要。

**END**

--------------------

![format_png 4][]

● [啥是布隆过滤器算法？][Link 1]

[● ][Link 2][从一道简单算法题理解快速排序的partition操作][partition]

● [视频动画|什么是快速排序？][Link 3]

● [动画: 快速排序|如何求第K大元素？][_K]

![format_png 5][]

点“在看”你懂得

![format_png 6][]

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9pY0hvZXJLTzNOakxHa0wzSmljWnh6WlVsTVBXYU9FVXRpYVZ5RHQ1QU9hSUpOa0xhbHRYT1lSaWFHU2J5aWJneFFzVkxSYXo5SnhmTjZLVkJtU05GYkZlNkx3LzY0MA?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2dpZi9ENjdwZWNlaWJlSVJiTkp1c21LYU5tck9QRTdjeDA3bUF3SWVDd1VmenY4T1RCWElOakNOaWJ6aGJJSGhjaWNmMkI5aWFXUUtEZDdkbjZwaWNPaWNZVVpwWUVwZy82NDA?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy80bFZiUUg0U2hpY1hjQklMSUx0MWJlV0tOMDliOWhHcjhLanR1RVk3MVg3SmVqamljZ3F2Q3JpYjBQdFh4Rko0dEhoRkVidFo2eWxaWnh1dVNCdU1DWThjQS82NDA?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy80bFZiUUg0U2hpY1hjQklMSUx0MWJlV0tOMDliOWhHcjh0THFIY29QY0FFRjR4OFFQcHJOQTUzN0dneTliSlBMVHFYMUR6bWg0aWJTVU5WSndpYWJaYWNMdy82NDA?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2dpZi9wNldsMkxETVFsSEM2cERYeVFSYVdqbFdSNVBJaHVrSVVHVjFuZks2SDlxdEhab3huWHRWZGV6dG9GZXhrYWV2dWRtWjFNYlY5cVdOWlRYaWFvcEx5b1EvNjQw?x-oss-process=image/format,png
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg%3D%3D&chksm=fa0e7f19cd79f60ff28c54da91fde37b0fbda83026ba6b3e693fd577fa78194b29e83ecf9bb8&idx=2&mid=2247487640&scene=21&sn=9aaeb095708efc55470466c194174da3#wechat_redirect
[Link 2]: http://mp.weixin.qq.com/s?__biz=Mzg2MzE5MjMxNQ%3D%3D&chksm=ce7ef418f9097d0e01bfe9410a9e40e9f4337c835c87e28332e6a8d8fd8b91b4794164f4c1a1&idx=1&mid=2247491980&scene=21&sn=5ef03c0108a5730fa28e492ec77e22d9#wechat_redirect
[partition]: https://blog.csdn.net/kexuanxiu1163/article/details/102675152
[Link 3]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg%3D%3D&chksm=fa0e61cecd79e8d8c11a11e3880b88727c5888cf998ee008cb2566ef5480ce94a812ca99813e&idx=3&mid=2247487055&scene=21&sn=e630f09ac077a1e55e14b5c5e79da923#wechat_redirect
[_K]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg%3D%3D&chksm=fa0e61c0cd79e8d6a47eb4dd9afa4770d23b45bf8d1dac8f79f55f01842c9d9722a2a1469267&idx=3&mid=2247487041&scene=21&sn=877cb6f770e00c454e841da2724b4f20#wechat_redirect
[format_png 5]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVJnTjYxb1pBaWFiNHpKOE9SbG03ektWY2lhUTFGRFFkSHFpYXA5UjlmTWRVM29BWkxiNEwxWk50dnFzeFFLbGljVkxpY0d4ekZ2NFRmV3BtQS82NDA?x-oss-process=image/format,png
[format_png 6]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9jNmdxbWhXaWFmeXI5djFSblJIZGdiRTlWTzljY2pWU0FuOGpxUXBoeUxKbDU5N1JzOUJ6RVViQlIwQUdmSmZ2a3pMOXJ1cWtUbVBBWHIyOXRISWNwRFEvNjQw?x-oss-process=image/format,png