algorithme pour nth_element [fermée]

Question

J'ai récemment découvert qu'il existe une méthode appelée nth_element dans le STL. Pour citer la description:

  

Nth_element est similaire à   partial_sort, en ce qu 'il partiellement   ordonne une série d'éléments: il   organise l'intervalle [first, last) de telle sorte   que l'élément pointé par le   nième itération est la même que la   élément qui serait dans cette position   si la gamme [premier, dernier) avait   été triés. De plus, aucun des   des éléments dans la gamme [n-ième, last) est   moins l'un des éléments de la   intervalle [first, n-ième).

Il revendique O (n) complexes en moyenne. Comment fonctionne l'algorithme? Je ne pouvais trouver aucune explication.

Answer 1

Il est appelé un algorithme de sélection et wikipedia a une page décente sur elle: http: //en.wikipedia. org / wiki / Selection_algorithm

lire également sur les statistiques de commande: http://en.wikipedia.org/wiki/Order_statistic

Answer 2

Très probablement la médiane de-terre-pleins algo.

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