0

在我接触到算法之前，我几乎已经了解了许多 STL 算法std::nth_element。我被困住了；我不知道它是如何工作的，它确实做到了。

为了教育和理解，有人可以向我解释算法是如何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是一种部分排序算法，它重新排列 [first, last) 中的元素，使得：

  • 如果 [first, last) 已排序，则 nth 指向的元素将更改为该位置将出现的任何元素。
  • 这个新的第 n 个元素之前的所有元素都小于或等于新的第 n 个元素之后的元素。更正式地说，nth_element 按升序对范围 [first, last) 进行部分排序，以便范围 [first, nth) 中的任何 i 和范围内的任何 j 都满足条件!(*j < *i)（对于第一个版本或第二个版本）comp(*j, *i) == false范围 [nth, last)。如果范围已完全排序，则放置在第 n 个位置的元素正是在该位置出现的元素。

nth 可能是结束迭代器，在这种情况下该函数无效。

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

2 回答 2

1

那么这里的第 n 个元素在哪里？

第 n 个元素是2at 索引2，因为这是您通过begin()+2.

如果 [first, last) 已排序，则 nth 指向的元素将更改为该位置将出现的任何元素。

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

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

您要求在索引 2（第 3 位）处具有第 3 大元素，这就是算法的作用。

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

!(*j < *i)（对于第一个版本，或comp(*j, *i) == false对于第二个版本）满足范围 [first, nth) 中的任何 i 和范围 [nth, last) 中的任何 j。

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

于 2021-09-18T00:30:03.633 回答
-1

在解决您的问题之前，我将先解释我的代码

例如我有这样的代码

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

并且不要忘记，数据必须从小到大排序（默认）

所以原来的数据

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之前的数据必须小于它，它之后的数据必须大于它

于 2021-09-19T02:09:02.737 回答