nth_element의 알고리즘

Question

나는 최근에 STL에 nth_element이라는 메서드가 있음을 알게되었습니다. 그것은 부분적 요소의 범위를 정렬 점에서

Nth_element가 partial_sort 유사하다 : 그것은 먼저 범위 [정렬 마지막) 등 요소가 반복자 가리키는 것으로 설명을 인용 전체 범위 [처음, 마지막]에 이 정렬 된 경우 에 해당하는 요소와 동일합니다. 또한 [nth, last] 범위의 요소 중 어느 것도 범위 [첫째, n 번째]에있는 요소보다 작은 이 아닙니다.

평균적으로 O (n) 복잡성을 주장합니다. 알고리즘은 어떻게 작동합니까? 나는 그것에 대한 설명을 찾을 수 없었다.

Answer 1

은 선택 알고리즘이라고하며 위키 피 디아 그것에 괜찮은 페이지가 있어요 : http://en.wikipedia.org/wiki/Selection_algorithm

는 또한 주문 통계에 대해 읽어 : http://en.wikipedia.org/wiki/Order_statistic

Answer 2

대부분의 경우 중간 수준의 중앙값은 너 한테.

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