算法nth_element [关闭]

Question

我最近发现，存在一个称为 nth_element 在该方法中STL。引述的描述：

  

Nth_element类似于   partial_sort，因为它部分地   定购一个范围的元素：它   排列范围[第一，最后一个）这样   该元件由指向   迭代第n是一样的   元件，这将是在该位置   如果整个范围[第一，最后一个）有   被排序。此外，没有任何的   在范围的元素[第n个，最后一个）是   小于任何在所述元件的   范围[第一，第n个）。

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

Answer 1

这就是所谓的选择算法和维基百科有一个体面的网页上： HTTP：//en.wikipedia。组织/维基/ Selection_algorithm

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

Answer 2

最有可能的中位数的位数ALGO。

http://en.wikipedia.org/wiki/Selection_algorithm #Linear_general_selection_algorithm _-_。22Median_of_Medians_algorithm.22