谷歌帮不上我的忙：两种选择算法，floydrivest算法和introselect，哪一种性能更好。
我假设这是floydrivest算法，但希望100%确定。
另外，如果还有更好的算法，我会很高兴听到它们的。
最佳答案
我认为弗洛伊德·里维斯更好
我最近为一个项目做了一些选择算法的研究。下面是每个算法的基本描述：
introselect：用一个轴执行数据的二分法。最初，选择一个简单的轴（如中间轴、中间轴等）。最坏情况下，简单轴通常为o（n^2），但平均为o（n）。如果递归级别超过某个阈值，我们将退回到中介轴的中间值。这是更昂贵的计算，但保证o（n）最坏的情况。
floyd rivest：使用两个枢轴执行数据的五分之一分区。选择这两个轴心点，使得第k个元素以高概率位于它们之间（这涉及随机采样数据，并通过递归选择第n个元素的上下两个元素）。当分区的大小变得足够小时，我们使用一种更简单的方法（如中值-3等）选择轴。
如你所见，两者非常相似。introselect从简单的轴开始，回到复杂的轴；floyd-rivest算法正好相反。主要的区别是introselect使用中间值，而floyd rivest使用递归采样技术。所以，我认为一个更好的比较是中位数与弗洛伊德里维斯。
哪个更好？根据我的研究，floyd-rivest的隐藏常数似乎小于中间带的中值。如果我没记错的话，中间带的中值需要5n比较（最坏情况），而floyd rivest只需要3.5n。floyd rivest也使用五进制方案，当数据可以有很多重复项时效果更好。introselect和floyd rivest对于小输入都减少到相同的算法，因此您应该在那里获得相似的性能（只要您实现它们相同）。在我的测试中，floyd-rivest比我尝试的所有其他选择算法都快20%。不过，我必须承认，我并没有测试introselect的正确实现，该实现会返回到中间值（我只是测试了libstdc++的伪introselect）。在最初的floyd-rivest论文中，他们自己（他们是medians方法的共同作者）说，medians的中值“很难实用”，floyd-rivest算法“可能是最好的实用选择”。
所以，在我看来，floyd rivest的旋转技术比中间带的中位数要好。您可以使用floyd rivest的旋转来实现introselect，但是您也可以只做一个纯粹的floyd rivest算法。我推荐Floyd Rivest作为最佳选择方法。
小心点！最初的floyd rivest论文给出了他们算法的一个示例实现（这是wikipedia上列出的实现，在编写本文时）。不过，这是一个简化版本。从我的测试来看，简化版实际上相当慢！如果你想快速实现，我想你需要实现完整的算法。我建议你读一下krzysztof c.kiwiel的论文《论floyd和rivest的选择算法》。他很好地描述了如何实现快速的floyd rivest选择。