相关疑难解决方法(0)

我最近发现在STL中存在一个名为nth_element的方法.引用描述:

Nth_element类似于partial_sort,因为它部分地对一系列元素进行排序:它排列范围[first,last],使得迭代器nth指向的元素与该位置中的元素相同(如果整个范围[第一个,最后一个]已经排序.另外,[nth,last]范围内的元素都不小于[first,nth]范围内的任何元素.

它声称平均具有O(n)复杂性.算法如何工作？我找不到任何解释.