algoritmo per nth_element [chiuso]

Question

Di recente ho scoperto che esiste un metodo chiamato nth_element nel STL. Per citare la descrizione:

  

nth_element è simile a   partial_sort, in quanto parzialmente   ordina una serie di elementi: it   organizza la gamma [first, last) tale   che l'elemento puntato dal   iteratore è ennesima uguale al   elemento che sarebbe in quella posizione   se l'intera gamma [primo, ultimo) aveva   stati ordinati. Inoltre, nessuno dei   elementi nell'intervallo [n-esimo, last) è   meno di qualsiasi degli elementi della   gamma [prima, ennesima).

E sostiene di avere O (n) la complessità in media. Come funziona l'algoritmo? Non riuscivo a trovare alcuna spiegazione.

Answer 1

Si chiama un algoritmo di selezione e di Wikipedia ha una pagina decente su di esso: http: //en.wikipedia. org / wiki / Selection_algorithm

Leggi anche statistiche d'ordine: http://en.wikipedia.org/wiki/Order_statistic

Answer 2

Molto probabilmente la mediana-di-mediane algo.

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