nth_element 是什么，它的作用是什么？以及如何实施

Question

在我达到算法std::nth_element之前，我几乎了解了很多STL算法。我坚持下去；我不知道它是如何工作的，但确实确实如此。

为了教育和理解，有人可以向我解释算法 std::nth_element 是如何工作的吗？

std::vector<int> v{ 9, 3, 6, 2, 1, 7, 8, 5, 4, 0 };
std::nth_element(v.begin(), v.begin() + 2, v.end());

for (auto i : v)
    std::cout << i << " ";
std::cout << '\n';

输出：

1 0 2 3 6 7 8 5 4 9

那么 nth 元素在哪里？
该算法如何以及做什么？
它是否进行某种部分排序？

这里是cppreference.com的一些解释：

nth_element is a partial sorting algorithm that rearranges elements in [first, last) such that:

The element pointed at by nth is changed to whatever element would occur in that position if [first, last) was sorted.

All of the elements before this new nth element are less than or equal to the elements after the new nth element. More formally, nth_element partially sorts the range [first, last) in ascending order so that the condition !(*j < *i) (for the first version, or comp(*j, *i) == false for the second version) is met for any i in the range [first, nth) and for any j in the range [nth, last). The element placed in the nth position is exactly the element that would occur in this position if the range was fully sorted.

nth may be the end iterator, in this case the function has no effect.

我仍然对此感到困惑。什么是第 n 个元素以及如何实现这样的可能算法？为了教育起见，我模仿了许多 STL 算法。非常感谢！

Answer 1

So where is nth element here?

第 n 个元素是索引 2 处的 2，因为那是您通过 begin()+2 时要求的。

The element pointed at by nth is changed to whatever element would occur in that position if [first, last) was sorted.

这意味着，如果对向量进行排序，则元素的顺序将为

0 1 2 3 4 5 6 7 8 9 
    ^--- begin() + 2

你要求在索引 2（第 3 个位置）处有第 3 个最大的元素，这就是算法所做的。

此外，它将所有较小的元素放在前面，所有较大的元素放在后面：

!(*j < *i) (for the first version, or comp(*j, *i) == false for the second version) is met for any i in the range [first, nth) and for any j in the range [nth, last).

让我们使用索引而不是迭代器，然后对于任何 i < 2 和任何 j > 2 它都认为 v[i] < v[j]。换句话说，1 和 0 都小于 2 3 6 7 8 5 4 9.

中的任何元素

Answer 2

在解决您的问题之前，我会先解释一下我的代码

例如我有这样的代码

int m_array_biasa[8] {3,2,10,45,33,56,23,47};

而且我正常使用它就像

std::nth_element(m_array_biasa, m_array_biasa + 4, m_array_biasa + 8);

所以这里的第n个元素是4[33]，std::nth_element的规则是第n个左边的数必须小于等于，右边的数必须大于第n

and don't forget, data must be sorted from small to large (default)

原来的数据是

3,2,10,45,33,56,23,47

改为

2 3 10 23 33 45 47 56

我的第n个是4[33]，所以上面的规则适用（不包括排序结果）

结果是

3 2 10 23 33 56 45 47

注意上面，33的位置没有变，但是有时候会有点混乱，比如我们把33改成1，那么结果

2 1 3 10 23 45 47 56

这里发生了什么，为什么数字1移动了（替换为23），为什么它不像之前的数字33一样，我之前说过我们必须先对数据进行排序（见上面的排序），原来索引nth[4]是数字23，那么数字1就换成了数字23，为什么要换呢，见nth_element规则

现在回答你的问题。

std::vector<int> v{ 9, 3, 6, 2, 1, 7, 8, 5, 4, 0 };
std::nth_element(v.begin(), v.begin() + 2, v.end());

v.begin()包含9，v.begin()+2包含6，记住，nth_element会先排序

0 1 2 3 4 5 6 7 8 9

你的输出是

1 0 2 3 6 7 8 5 4 9

上面的第n个[2]（根据你的v.begin() + 2）p是2，所以这里的2就像是其他数据的参考，2之前的数据肯定小于它，并且之后肯定不止它

nth_element 是什么，它的作用是什么？以及如何实施

What is nth_element and what does it do exactly? and how to implement it

c++

algorithm

nth-element