алгоритм для nth_element

Question

Недавно я узнал, что в STL существует метод, называемый nth_element. Процитируем описание:

Nth_element похож на partial_sort, в том, что она частично заказывает ряд элементов: он организует диапазон [первый, последний), такие , что элемент, на который указывает итератора nth совпадает с элементом , который был бы в этом положении , если был отсортирован весь диапазон [первый, последний] . Кроме того, ни один из элементов в диапазоне [nth, last) не является меньше любого из элементов в диапазоне [первый, n-й).

Он утверждает, что в среднем имеет сложность O (n). Как работает алгоритм? Я не мог найти объяснений.

Answer 1

Это называется алгоритмом выбора и википедия имеет приличную страницу на нем: http://en.wikipedia.org/wiki/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