分享一个小优化
2026-10-11 22:01:11
发布于：吉林
我发现了一个快速选择算法的优化，可以保证其时间复杂度最坏为 。
具体怎么操作呢？
首先，想到一种解决快速选择解决的问题的算法：可以二分第 大/小，判断有多少个数大于/小于他。这应该是很好写的，相信大家都会。
它可以保证时间复杂度为 ，其中 为值域。
而我们利用这样的思想，把统计有多少个数大于/小于当前的 改成以 为基准值跑快速排序中的算法——将小于它的放前面，将大于它的放后面——这样我们用相同的时间复杂度完成了计算大于/小于当前的 所不能完成的事情，而它能完成的事情我们也都能完成。
然后，我们通用快速选择的框架去跑二分查找——递归不仅传入当前区间的左右端点，同时传入二分的 和 ，每次以 为基准值。这样，我们既保住了二分查找的最坏 ，也保住了快速选择的平均 。
这里有几个小优化可以提一下：
- 我们不是一定要传入 和 ，我们可以每次取当前区间的最大值与最小值的平均值作为基准值。这样只会更快。为什么呢？因为每次二分本质上是值域范围的减半，而由于当前的最大/小值一定小于/大于上一轮的 ，因此用当前的最值只会让值域减少的更多，让算法更快。
- 我们可以使用三路分区/荷兰国旗算法优化此问题，具体的你问AI去。
不贴代码。
我们也可以这么去做快速排序，最坏时间复杂度是一样的，最好则等同于原本—— 。
但是，我要指明，这可能看上去很好看，但是实际写起来并不如一些其他写法，例如随机化的快速选择/快速排序就可以达到期望 / ，甚至你可以直接用C++原生的nth_element/sort函数，一行，却能实现我们写数十行也达不到的速度……
但是，我们注意到，sort函数的源码中会在递归深度> 后才切换到堆排序，因此我们可以得知sort最坏情况下是 ，而我们的 一般在1e5左右，这种情况下， 约为 ，因此 ，因此如果排序int的话我们似乎可以比sort还要快一点……
但是，我又要说，我们没有细算这之中的常数——我的算法中还额外进行了一次求最值的过程。因此，如果真的算上常数，我的方法未必会有sort快，况且sort还有最终插入排序，因此，我认为，我们也可以对我们的现有算法进行改进：如果递归深度较大且 ，那么就切换为堆排序；如果 某阈值，那么直接跳出递归，等候插入排序处理。这样，我们完成了对算法的重大改革。这是算法界的一小步，我的一大步。
有帮助，赞一个