c++ - std::nth_element 和 std::sort 之间的实际区别是什么？

Question

我一直在研究 std::nth_element 算法，显然:

Rearranges the elements in the range [first,last), in such a way that the element at the resulting nth position is the element that would be in that position in a sorted sequence, with none of the elements preceding it being greater and none of the elements following it smaller than it. Neither the elements preceding it nor the elements following it are guaranteed to be ordered.

但是，使用我的编译器，运行以下命令:

    vector<int> myvector;
    srand(GetTickCount());

    // set some values:
    for ( int i = 0; i < 10; i++ )
        myvector.push_back(rand());

    // nth_element around the 4th element
    nth_element (myvector.begin(), myvector.begin()+4, myvector.end());

    // print results
    for (auto it=myvector.begin(); it!=myvector.end(); ++it)
        cout << " " << *it;

    cout << endl;

总是以与 std::sort 完全相同的方式返回一个完全排序的整数列表。我错过了什么吗？这个算法有什么用？

编辑:好的，下面使用更大集合的示例表明存在很大差异:

    vector<int> myvector;
    srand(GetTickCount());

    // set some values:
    for ( int i = 0; i < RAND_MAX; i++ )
        myvector.push_back(rand());

    // nth_element around the 4th element
    nth_element (myvector.begin(), myvector.begin()+rand(), myvector.end());

    vector<int> copy = myvector;
    std::sort(myvector.begin(), myvector.end());

    cout << (myvector == copy ? "true" : "false") << endl;

Answer 1

对于 std::nth_element 完全有效对整个范围进行排序以实现记录的语义 - 但是，这样做将无法满足所需的复杂性(线性)。关键是它可以这样做，但它没有必须。

这意味着 std::nth_element 可以提前退出 - 只要它可以告诉你范围的 n'th 元素将是什么，它可以停下来。例如，对于一个范围

[9,3,6,2,1,7,8,5,4,0]

要求它给你第四个元素可能会产生类似

[2,0,1,3,8,5,6,9,7,4]

列表是部分排序的，刚好可以判断出第四个元素是3。

因此，如果您想回答“哪个数字是第四小的”或“哪个是四个最小的数字”，那么 std::nth_element 就是您的 friend 。

如果您想按顺序获得四个最小的数字，您可能需要考虑使用 std::partial_sort .