STL排序与中位数

Question

sort ()使用根据当前分区比率在快速排序和堆排序之间切换的Introsort algorithm 。

实现中间数快速排序代替内部排序有什么实际的缺点吗？毕竟，理论上很难对混合的排序算法进行建模并计算它们的最坏情况的复杂度--尽管我假设Introsort的复杂度为O(N log N)。

Answer 1

参见Musser关于Introsort的原始论文。基本上，虽然Medians和Introsort的中位数是渐近相同的，但Introsort对每个项目做的恒定工作更少，而且通常更快。论文确实提到了中位数作为后备排序而不是堆排序是可以的。

大卫·R·马瑟。内省排序和选择算法。[Postscript version]

Answer 2

据我所知，Quicksort在排序或非常接近排序的集合上性能很差- O(n^2)。查看维基百科在Introsort上的页面-关于Introsort和Quicksort的令人信服的统计数据。