STL排序vs中位数

std :: sort（）使用Introsort algorithm在快速&之间切换，取决于当前的分区比率。STL排序vs中位数

实施中位数的Medians Quicksort代替Introsort是否存在实际的缺点？毕竟，理论上排序算法的混合模型很难计算其最坏情况下的复杂度 - 尽管我假设Introsort的是O（N log N）。

2010-09-18 PKG

不确定你的问题在这里？ – 2010-09-18 03:17:55

可以下降的人解释为什么？这个问题应该清楚：实施中位数Medians Quicksort代替Introsort是否存在实际的缺点？有人已经给出了答案。 – PKG 2011-04-06 19:34:26

查看Musser在Introsort上的原始论文。基本上，虽然Medians和Introsort的中位数渐近地相同，但Introsort每个项目的工作量不大，并且通常更快。该文件确实提到了Medians中位数可以作为备用排序而不是堆排序。

David R. Musser。反演分类和选择算法。 [Postscript version]

2012-02-26 00:57:20 xan

从我记忆中，Quicksort在排序或非常接近排序的集合上执行的效果很差 - O（n^2）。查看维基百科的页面Introsort - 有关Introsort vs. Quicksort的引人注目的统计数据。

2010-09-18 03:59:57

Quicksort的中位数版本的中位数最坏的情况是O（n log n）并且是最坏的情况下最佳的 – PKG 2010-09-20 06:12:09

我的不好 - 我没有意识到这一点，谢谢user356106。我想实现中位数的中位数，看看它如何表现与明确的答案introsort。 – 2010-09-20 06:45:12

回答