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

回答