使用 stdnth 元素查找中位数(或其他分位数)

所述 std::nth_element 算法需要三个迭代器:一个迭代开始时, N 个位置,并结束。一旦函数返回,第 n 个元素(按顺序)将是第 n 个最小元素。 (该函数具有更复杂的重载,例如,一些采用比较函子;请参阅上面的链接了解所有变体。)

注意此功能非常有效 - 它具有线性复杂性。

为了这个例子,让我们将长度为 n 的序列的中位数定义为位置为⌈n/2⌉的元素。例如,长度为 5 的序列的中值是第 3 个最小元素,长度为 6 的序列的中值也是如此。

要使用此函数查找中位数,我们可以使用以下内容。假设我们开始

std::vector<int> v{5, 1, 2, 3, 4};    

std::vector<int>::iterator b = v.begin();
std::vector<int>::iterator e = v.end();

std::vector<int>::iterator med = b;
std::advance(med, v.size() / 2); 

// This makes the 2nd position hold the median.
std::nth_element(b, med, e);    

// The median is now at v[2].

为了找到第 p分位数 ,我们将改变上面的一些行:

const std::size_t pos = p * std::distance(b, e);

std::advance(nth, pos);

并在 pos 处寻找分位数。