алгоритм для nth_Element [закрыто

Question

Я недавно узнал, что существует метод под названием nth_element. в STL. Чтобы процитировать описание:

Nth_Element аналогичен partial_sort, в том, что он частично заказывает диапазон элементов: он устраивает диапазон [первый, последний), такой, что элемент, указанный на ITERATOR NT, совпадает с элементом, который был бы в этом положении, если весь Диапазон [первый, последний) был отсортирован. Кроме того, ни один из элементов в диапазоне [NTH, последних) меньше, чем любой из элементов в диапазоне [First, nth).

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

Answer 1

Это называется алгоритм выбора, а Wikipedia имеет приличную страницу на нем: 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_selice_algorithm_-_.22median_of_medians_algorithm.22.