c++ - 第 n 个元素的算法

Question

我最近发现在 STL中有一个名为nth_element的方法。引用描述：

Nth_element 类似于 partial_sort，因为它对一系列元素进行部分排序：它排列范围 [first, last) 使得迭代器 nth 指向的元素与如果整个元素位于该位置的元素相同range [first, last) 已排序。此外，范围 [nth, last) 中的任何元素都不小于范围 [first, nth) 中的任何元素。

它声称平均具有 O(n) 复杂度。算法是如何工作的？我找不到任何解释。

Answer 1

它被称为选择算法，维基百科上有一个不错的页面：http ://en.wikipedia.org/wiki/Selection_algorithm

另请阅读订单统计信息：http ://en.wikipedia.org/wiki/Order_statistic

Answer 2

很可能是中位数算法的中位数。

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