预期运行时间为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，使最坏的情况不太可能发生，但并非不可能。
602392714
清零编程群