我几乎已经理解了许多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)中的元素，使:
- 第n位所指向的元素被更改为[first, last]排序后在该位置出现的元素。
- 新第n个元素之前的所有元素都小于或等于新第n个元素之后的元素。更正式地说，nth_element按升序对范围[first, last]进行部分排序，以便对范围[first, n]中的任何i和范围[n, last]中的任何j满足条件
!(*j < *i)(对于第一个版本，或对于第二个版本满足条件comp(*j, *i) == false)。放置在第n个位置的元素正是在该范围完全排序后在该位置出现的元素。n可以是end迭代器，在这种情况下，函数不起作用。
- 我还是很困惑。第n个元素是什么，如何实现这样一个可能的算法?为了便于教学，我模仿了许多STL算法。非常感谢!
那么第n个元素在哪里呢?
第n个元素是索引为2的2，因为这是你传递begin()+2时所要求的。
第n位所指向的元素被改成[first, last]排序后在该位置出现的元素
这意味着，如果对vector进行排序，则元素的顺序为
0 1 2 3 4 5 6 7 8 9
^--- begin() + 2
你要求在索引2(第三个位置)有第三大的元素，这就是算法所做的。
另外，它把所有较小的元素放在前面，所有较大的元素放在后面:
!(*j < *i)(对于第一个版本，或者对于第二个版本comp(*j, *i) == false)对于范围[first, n]中的任何i和范围[nth, last]中的任何j都满足
让我们使用下标而不是迭代器，那么对于任何i < 2和j > 2，它都保存v[i] < v[j]。换句话说，1和0都小于2 3 6 7 8 5 4 9中的任何元素。
在讨论你的问题之前，我先解释一下我的代码
例如，我有这样的代码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
右边的数必须大于n别忘了，数据必须从小到大排序(默认)
也就是原来的数据
3 2 10, 45岁,33岁,56岁,23岁,47个
更改为
2 3 10 23 33 45 47 56
my NTH是4[33]，所以上述规则适用(不包括排序结果)
，结果是
3 2 10 23 33 56 45 47
上面的注意，位置33没有改变，但有时它有点令人困惑，例如我们将33改为1，然后结果
2 1 3 10 23 45 47 56
这里发生了什么，为什么数字1移动了(被23取代了)，为什么它不像之前的数字33一样，我之前说过我们必须先对数据进行排序(参见上面的排序)，结果是索引n[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之前的数据必须小于它，在它之后的数据必须大于它