Algorithmus für nth_element

Question

Ich habe kürzlich herausgefunden, dass es eine Methode namens nth_element in der STL gibt. Zitieren die Beschreibung:

nth_element ähnelt partial_sort, dass sie teilweise eine Reihe von Elementen anordnet: es den Bereich anordnet [erste, letzte) so , dass das Element, auf das durch den Iterator nth ist dasselbe wie das Element, das in dieser Position wäre, wenn der gesamte Bereich [zuerst, zuletzt] sortiert worden wäre. Außerdem ist keines der Elemente im Bereich [nth, last) weniger als eines der Elemente im Bereich [erste, n-te].

Es wird behauptet, dass es im Durchschnitt O (n) -Komplexität hat. Wie funktioniert der Algorithmus? Ich konnte keine Erklärung dafür finden.

Answer 1

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

auch über Auftragsstatistiken lesen: http://en.wikipedia.org/wiki/Order_statistic

Answer 2

Höchstwahrscheinlich wird der Median-of-Mediane Algo.

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