我假设它是FloydRivest算法,但想要100％肯定.
此外,如果为此目的存在更好的算法,我很高兴听到它们.
TLDR;我认为Floyd-Rivest更好我最近对我正在进行的项目的选择算法做了一些研究.以下是每种算法的基本描述：
> Introselect：使用单个数据透视表对数据进行二分法.最初,选择简单的枢轴(例如,中间,3的中间等).在最坏的情况下,简单的枢轴通常为O(n ^ 2),但平均为O(n).如果递归级别超过某个阈值,我们将回退到中位数中位数.计算成本更高,但保证O(n)最坏的情况.
> Floyd-Rivest：使用两个支点执行数据的五元分区.选择两个枢轴使得第k个元素位于它们之间,具有高概率(这涉及随机采样数据,并通过递归选择两个元素,在第n个元素的上方和下方).当分区的大小变得足够小时,我们使用更简单的方法选择枢轴(例如,中位数为3等)
如您所见,两者非常相似. Introselect从简单的枢轴开始,回到复杂的枢轴; Floyd-Rivest算法正好相反.主要区别在于introselect使用中位数中位数,而Floyd-Rivest使用递归采样技术.因此,我认为更好的比较是中位数与Floyd-Rivest的中位数.
哪个更好？从我的研究来看,Floyd-Rivest隐藏的常数似乎小于中位数的中位数.如果我没记错的话,中位数中位数需要5n比较(最差情况),而Floyd-Rivest只需要3.5n. Floyd-Rivest也使用了一个五元方案,当数据有很多重复时,这个方案更好. introselect和Floyd-Rivest都会针对小输入减少相同的算法,因此您应该在那里获得类似的性能(只要您实现它们相同).在我的测试中,Floyd-Rivest比我尝试的所有其他选择算法快20％.虽然,我必须承认,我没有测试反对中间选择的正确实现,这些内部回归到中位数中位数(我刚刚测试了libstdc的伪内向性).在最初的Floyd-Rivest论文中,他们自己(他们是中位数中位数的合着者)说中位数的中位数“几乎不实用”,并且Floyd-Rivest算法“可能是最实用的选择”.
因此,在我看来,Floyd-Rivest的旋转技术优于中位数中位数.你可以使用Floyd-Rivest的旋转来实现introselect,但是你也可以做一个纯粹的Floyd-Rivest算法.我推荐Floyd-Rivest作为最佳选择方法.
被警告！最初的Floyd-Rivest论文给出了他们算法的一个示例实现(这是在撰写本文时维基百科上列出的实现).但是,这是一个简化版本.从我的测试来看,简化版本实际上非常慢！如果你想快速实现,我认为你需要实现完整的算法.我建议阅读Krzysztof C. Kiwiel的论文“On Floyd和Rivest的SELECT算法”.他对如何实现快速Floyd-Rivest选择进行了很好的描述.