有谁知道不同实现的预期运行时间和最坏情况下的运行时间std::nth_element？我几乎每天都使用这个算法。
我对最近的 Microsoft 编译器附带的 STL 版本特别感兴趣，但有关此主题的任何信息都是有帮助的。
请注意，这不是这个问题的重复。我了解存在哪些算法，但我对哪些实现使用哪些算法感兴趣。
作为背景，有众所周知的算法可以做到这一点。一种是 O(n) 平均情况和 O(n log n) 最坏情况，一种是 O(n) 最坏情况但在实践中很慢（中位数的中位数）。另请注意，有一些有趣的实现策略可以在实践中快速获得最坏情况的 O(n) 运行时间。标准说这必须是更糟糕的 O(n) 平均时间。
预期的运行时间是 O(N) 大多数实现的最坏情况的运行时间是 O(N * N)，因为大多数实现都使用 QuickSelect 并且可能是 QuickSelect 运行到错误的分区中。对于 Microsoft VS2008、VS2010 和 VS2012 来说也是如此。
现在有了新的 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) 行为。QuickSelect 可以通过使用抽样来改进，使最坏的情况不太可能发生但并非不可能。
cppreference说，首先它排序然后找到第 n 个元素，但是通过这种方式平均值应该是O(n log n)（通过基于比较的排序算法），但他们写的平均值是 O(n)，除了使用像基数排序这样的排序之外似乎不正确，...但是因为它具有基于通用比较的输入，似乎不可能使用基数排序或任何其他不基于比较的排序。无论如何，在实践中使用快速排序算法比使用普通选择算法更好（内存和平均时间）。