有谁知道不同实现的预期运行时间和最坏情况运行时间std::nth_element？我几乎每天都使用这种算法。
std::nth_element
我对最近Microsoft Compilers附带的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），并且不会出现更糟的情况，因为使用了DavidMusser的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，使最坏的情况不太可能发生，但并非不可能。
