我最近发现，存在一个名为 nth_element 在STL方法。引述说明：

I have recently found out that there exists a method called nth_element in the STL. To quote the description:

Nth_element类似于   partial_sort，因为它部分地   承揽了一系列的元素：它   排列范围[第一个，最后一个），例如   该元素由指向   迭代的第n个相同的   元素，这将是在那个位置   如果整个区间[first，last）中有   被排序。此外，没有任何的   范围内的元素[n次，最后一次）是   小于任何在元素   范围[第一次，第n次）。

Nth_element is similar to partial_sort, in that it partially orders a range of elements: it arranges the range [first, last) such that the element pointed to by the iterator nth is the same as the element that would be in that position if the entire range [first, last) had been sorted. Additionally, none of the elements in the range [nth, last) is less than any of the elements in the range [first, nth).

这号称有平均为O（n）的复杂性。如何算法的工作？我找不到它的任何解释。

It claims to have O(n) complexity on average. How does the algorithm work? I could not find any explanation for it.

推荐答案

这就是所谓的一个选择算法和维基百科有一个体面的页面就可以了：http://en.wikipedia.org/wiki/Selection_algorithm

It's called a selection algorithm and wikipedia has a decent page on it: http://en.wikipedia.org/wiki/Selection_algorithm

另外阅读顺序统计：http://en.wikipedia.org/wiki/Order_statistic