Algorithmus für nth_element [geschlossen]

Question

Ich habe vor kurzem festgestellt, dass ein Verfahren existiert namens nth_element in der STL. Um die Beschreibung zu zitieren:

  

ist nth_element ähnlich wie   partial_sort, dass er teilweise in   ordnet eine Reihe von Elementen: es   ordnet den Bereich [first, last), wie   dass das Element, auf die der zu   Iterator ist nth das gleiche wie die   Element, das in dieser Position sein würde,   wenn der gesamte Bereich [first, last) hatte   wurden sortiert. Darüber hinaus keine der   Elemente im Bereich [n-ten, liest) ist   weniger als alle der Elemente in der   Bereich [first, n-te).

Sie behauptet, O (n) Komplexität im Durchschnitt zu haben. Wie funktioniert der Algorithmus funktioniert? Ich konnte keine Erklärung dafür finden.

Answer 1

Es ist eine Auswahl Algorithmus genannt und wikipedia hat eine gute Seite darauf: http: //en.wikipedia. org / wiki / Selection_algorithm

Auch über Auftragsstatistik lesen: http://en.wikipedia.org/wiki/Order_statistic

Answer 2

Wahrscheinlich der Median-of-Mediane Algo.

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