std::nth_element的作用、工作原理及实现方法详解

1. 测试代码中的nth元素对应位置 #

你代码中传入std::nth_element的第二个参数是v.begin() + 2，这个迭代器指向的位置就是nth位置，对应数组下标为2的元素。
你的测试数组全排序后结果为0 1 2 3 4 5 6 7 8 9，下标2对应的元素值为2，你的输出结果中下标2的位置也确实是2，符合算法的预期效果。

2. 具体工作逻辑 #

std::nth_element 底层通常基于*快速选择（Quickselect）*算法实现，部分STL实现（如GCC的libstdc++）会采用内省选择（Introspective Selection）优化，避免极端输入下的最坏时间复杂度。
核心执行步骤如下：

• 从区间中选取基准值pivot，优化实现通常会采用三数取中、中位数采样等策略选择pivot，避免最坏情况
• 对区间做分区操作：将所有小于等于pivot的元素放到pivot左侧，大于等于pivot的元素放到右侧，得到pivot所在的位置pos
• 比较pos和目标nth位置：
  • 若pos == nth：算法直接结束，此时nth位置已经是全排序后对应的值
  • 若pos < nth：仅需要在pos右侧的子区间重复上述操作
  • 若pos > nth：仅需要在pos左侧的子区间重复上述操作
    算法不需要对左右子区间内部做排序，仅保证nth位置正确，且左侧所有元素不大于右侧所有元素即可，因此平均时间复杂度为O(n)，远低于全排序的O(nlogn)。

3. 是否属于部分排序类算法 #

是，std::nth_element 属于典型的部分排序算法，它不需要对整个区间做全排序，仅满足部分排序约束即可。

简易模拟实现参考 #

你可以参考以下基于快速选择的简易实现，用于理解算法逻辑：

#include <vector>
#include <algorithm>

template <typename Iter, typename Comp = std::less<>>
void my_nth_element(Iter first, Iter nth, Iter last, Comp comp = Comp{}) {
    if (first == last || nth == last) {
        return;
    }
    while (std::next(first) != last) {
        // 此处简化取末尾元素为pivot，生产级实现需要优化pivot选取逻辑
        Iter pivot_iter = std::prev(last);
        Iter partition_pos = std::partition(first, pivot_iter, [&](const auto& val) {
            return comp(val, *pivot_iter);
        });
        std::swap(*partition_pos, *pivot_iter);
        
        if (partition_pos == nth) {
            return;
        } else if (nth < partition_pos) {
            last = partition_pos;
        } else {
            first = std::next(partition_pos);
        }
    }
}

内容的提问来源于stack exchange，提问作者Itachi Uchiwa