如何用std::nth_element实现部分排序？为何结果不符合预期？

你对std::nth_element的功能存在认知偏差，这个函数不会将前半部分元素完全排序，它的核心作用是：

• 把你指定的middle迭代器指向的元素，放到它在完整降序排序后的正确位置（这里是值为5的元素，对应索引4）
• 保证middle左侧的所有元素都不小于该位置的元素（降序规则下）
• 保证middle右侧的所有元素都不大于该位置的元素
• 但左侧和右侧的内部元素是无序的，不需要满足完全排序的要求

看你的实际输出，5确实处在正确位置，左边的6、7、9、8都不小于5，右边的4、1、2、0、3都不大于5，这完全符合std::nth_element的标准行为。

如果想要得到前半部分完全降序的结果，你需要在nth_element执行完成后，对前半部分单独调用排序函数。修改后的代码如下：

#include <bits/stdc++.h>
using namespace std;

void print(vector<int>data)
{
     for(int i:data)
         cout<<i<<" ";
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r+", stdin);
    freopen("output.txt", "w+", stdout);
#endif
    vector<int> v({5,7,4,2,8,6,1,9,0,3});
    auto middle=v.begin()+v.size()/2;
    nth_element(v.begin(), middle ,v.end(), greater<int>());
    // 对前半部分执行完全降序排序
    sort(v.begin(), middle, greater<int>());
    print(v);
}

执行这段代码后，输出就会符合你的预期：9 8 7 6 5 4 1 2 0 3

总结 #

• std::nth_element是高效的元素选择算法，仅保证指定位置元素正确、左右部分满足大小关系，不保证内部有序
• 若需要前n个元素完全有序，需在nth_element后对目标区间调用sort

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