有谁知道不同std::nth_element实现的预期运行时间和最坏情况的运行时间？ 我几乎每天都使用这个算法。
我对最新的Microsoft编译器附带的 STL 版本特别感兴趣，但有关此主题的任何信息都是有帮助的。
请注意，这不是这个问题的重复。我了解存在哪些算法，但我对哪些实现使用哪些算法感兴趣。
对于背景，有众所周知的算法可以做到这一点。 一个是O（n）平均情况和O（n log n）最坏情况，一个是O（n）最坏情况，但在实践中很慢（中位数）。另请注意，有人谈论有趣的实现策略，以获得在实践中快速的最坏情况 O（n） 运行时间。 该标准规定，这一定是在更差的O（n）平均时间。
预期运行时间为 O（N）大多数实现的最坏情况运行时间是 O（N * N），因为大多数实现都使用快速选择，并且可能是快速选择遇到坏分区。VS2008、VS2010和VS2012 Microsoft也是如此。
现在，随着新的ISO C++ 2011标准，std：：sort的复杂性已经收紧 - 它保证为O（N * log N），并且没有更糟糕的情况，因为使用了David Musser的IntroSort： - 使用QuickSort，如果数组的某些部分遇到错误的分区，则交换到堆排序。
理想情况下，完全相同的 std：：nth_element 但 ISO C++ 2011 标准并未收紧复杂性要求。所以std：：nth_element在最坏的情况下可能是O（N * N）。这可能是因为在David Musser的原始论文中（见这里），他没有提到如果QuickSelect变坏了应该换成什么算法。
在最坏的情况下，可以使用使用 5 组的中位数（我看过一篇论文推荐的 7 组，但找不到）。因此，std：：nth_element 的质量实现可以使用 QuickSelect 并在分区出现问题时交换为中位数。这将保证O（N）行为。快速选择可以通过使用采样来改进，使最坏的情况不太可能，但并非不可能。
GCC 4.7 中的实现使用了 David Musser 的内省选择（这里有他的论文详细介绍了 introsort 和 introselect）。根据这些文件，最坏情况的执行时间为O（n）。
cppreference 说，首先它排序，然后找到第 n 个元素，但通过这种方式，平均值应该O(n log n)（通过基于比较的排序算法），但他们写的平均值是 O（n），除了使用基数排序之类的排序之外，似乎不正确，...但是因为它具有基于通用比较的输入，似乎不可能使用基数排序或任何其他不基于比较的排序。无论如何，在实践中使用快速排序算法比使用普通选择算法（内存和平均时间）更好。