nth_element


类别：算法	组件类型：函数

原型

Nth_element是重载名称；实际上有两种nth_element函数。

template <class RandomAccessIterator>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
                 RandomAccessIterator last);

template <class RandomAccessIterator, class StrictWeakOrdering>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
                 RandomAccessIterator last, StrictWeakOrdering comp);

说明

Nth_element类似于partial_sort，因为它对一系列元素进行部分排序：它按如下方式排列范围[first, last)，使得迭代器nth所指的元素与整个范围经排序后该元素所在位置的元素相同[first, last)此外，范围内没有元素[nth, last)小于范围内任何元素[first, nth). [1]

两个版本nth_element在如何定义一个元素是否小于另一个元素方面有所不同。第一个版本使用operator<比较对象，第二个版本使用函数对象comp.

第一个版本的后置条件nth_element如下：范围内没有迭代器i使得[first, nth)*nth < *i，且没有迭代器j[nth + 1, last)使得*j < *nth*nth < *i第二个版本的后置条件.

comp(*nth, *i)nth_element如下：范围内没有迭代器i使得[first, nth)*nth < *i为真comp(*j, *nth)j[nth + 1, last)使得*j < *nth*nth < *i定义真comp(*j, *nth).

在标准头 algorithm 中和非标准向后兼容头 algo.h 中定义。

对类型的要求

对于第一个版本，即采用三个参数的版本

RandomAccessIterator

是随机访问迭代器的模型。是可变的。
是随机访问迭代器的模型。的值类型是 LessThan Comparable。
是随机访问迭代器的模型。在
的值类型上的排序关系是一种严格的弱排序，如 LessThan Comparable 要求中定义。是随机访问迭代器的模型。对于第二个版本，即采用四个参数的版本

StrictWeakOrdering

是随机访问迭代器的模型。是可变的。
是随机访问迭代器的模型。的值类型是 LessThan Comparable。
是严格弱排序的模型。的值类型可转换为
是随机访问迭代器的模型。的参数类型。是严格弱排序的模型。前提条件

是有效范围。

[first, nth)（根据这两个条件
[nth, last)（根据这两个条件

是有效范围。）[first, last)复杂度

平均为

线性last - first. [2]

示例

int A[] = {7, 2, 6, 11, 9, 3, 12, 10, 8, 4, 1, 5};
const int N = sizeof(A) / sizeof(int);

nth_element(A, A + 6, A + N);
copy(A, A + N, ostream_iterator<int>(cout, " "));
// The printed result is "5 2 6 1 4 3 7 8 9 10 11 12".

说明

[1] 这与partial_sort不同的方式是范围[first, nth)和范围[nth, last)无序：仅保证[nth, last)中没有元素小于[first, nth)中的任何元素。在该意义上，nth_element更类似于partition而不是sort. Nth_element的工作量小于partial_sort，所以合理的来说，这一点更快。这是使用它的主要原因nth_element的替代partial_sort.

[2] 请注意，这明显低于partial_sort.

另请参阅

partial_sort, partition, sort, StrictWeakOrdering, LessThan Comparable