algoritmo para nth_element [cerrado]

Question

He descubierto recientemente que existe un método llamado nth_element en el STL. Para citar la descripción:

  

Nth_element es similar a   partial_sort, en que parcialmente   ordena una serie de elementos: se   organiza el rango [primero, último) tal   que el elemento apuntado por el   iterador n-ésimo es el mismo que el   elemento que estar en esa posición   si todo el rango [primero, último) tenía   sido ordenados. Además, ninguna de las   elementos en el rango [n-ésimo, última) es   menos de cualquiera de los elementos de la   rango [primero, de orden n).

Se afirma que tiene O (n) la complejidad en promedio. ¿Cómo funciona el algoritmo? No pude encontrar ninguna explicación para ello.

Answer 1

Se llama un algoritmo de selección y Wikipedia tiene una página decente en él: http: //en.wikipedia. org / wiki / Selection_algorithm

También leer sobre estadísticas de orden: http://en.wikipedia.org/wiki/Order_statistic

Answer 2

Lo más probable es la mediana de las medianas-algo.

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