27

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

重新排列范围 [first,last) 中的元素，使得结果第 n 个位置的元素是排序序列中该位置的元素，其前面的元素没有一个更大，也没有一个它后面的元素比它小。它前面的元素和它后面的元素都不能保证是有序的。

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

    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;
4

4 回答 4

53

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您就是朋友。

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

于 2012-04-27T14:28:59.383 回答
10

std::nth_element 的实现如下所示：

void _Nth_element(_RanIt _First, _RanIt _Nth, _RanIt _Last, _Pr _Pred)
{
    for (; _ISORT_MAX < _Last - _First; )
        {   // divide and conquer, ordering partition containing Nth
        pair<_RanIt, _RanIt> _Mid =
            _Unguarded_partition(_First, _Last, _Pred);

        if (_Mid.second <= _Nth)
            _First = _Mid.second;
        else if (_Mid.first <= _Nth)
            return; // Nth inside fat pivot, done
        else
            _Last = _Mid.first;
        }

    _Insertion_sort(_First, _Last, _Pred);  // sort any remainder
}

其中 ISORT_MAX 定义为 32。

因此，如果您的序列超过 32 个元素，它只会对其执行 InsertionSort。因此，您的短序列已完全排序。

于 2014-11-04T18:48:20.573 回答
7

std::sort对所有元素进行排序。std::nth_elenemt没有。它只是将第 n 个元素放在第 n 个位置，一侧有较小或相等的元素，另一侧有较大或相等的元素。如果您想找到第 n 个元素（显然）或者如果您想要 n 个最小或最大的元素，则使用它。完整的排序满足这些要求。

那么为什么不直接执行完整排序并获取第 n 个元素呢？因为std::nth_element要求复杂度为 O(N)，而复杂度std::sort为 O(Nlog(N))。std::sort不能满足复杂度要求std::nth_element。如果您不需要对范围进行完整排序，则使用它是有利的。

至于你的例子，当我在 GCC 4.7 上运行类似的代码时，我得到了预期的结果：

  for ( int i = 0; i < 10; i++ )
    myvector.push_back(rand()%32); // make the numbers small

  cout << myvector << "\n";
// nth_element around the 4th element
  nth_element (myvector.begin(), myvector.begin()+4, myvector.end());
  cout << myvector << "\n";
  std::sort(myvector.begin(), myvector.end());
  cout << myvector << "\n";

生产

{ 7, 6, 9, 19, 17, 31, 10, 12, 9, 13 }
{ 9, 6, 9, 7, 10, 12, 13, 31, 17, 19 }
{ 6, 7, 9, 9, 10, 12, 13, 17, 19, 31 }
               ^

我使用定制ostream operator<<打印出结果的地方。

于 2012-04-27T14:27:31.907 回答
0

我比较了 std::sort 与 std::nth_element 在随机无符号 long long 的大向量 (512MB) 上运行并取其中间元素时的执行时间。是的，我知道它是 O(N log(N)) 与 O(N)，无论如何我希望 std::nth_element(mid) 的速度大约是 std::sort 的两倍，因为它应该对“排序”大约一半的元素。结果让我有点惊讶，这就是我分享它们的原因：

timeSort = 217407 (msec)
timeNthElement = 18218 (msec)

std::sort 慢了大约 12 倍

这是我使用的一段代码（它使用的是 windows.h）：

#include <windows.h>
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <random>

int main()
{
    static const size_t NUMELEM = 512 * 1024 * 1024;
    static const size_t NUMITER = 3;
    std::vector<unsigned long long> vec1(NUMELEM);
    std::vector<unsigned long long> vec2(NUMELEM);
    std::random_device rd;
    std::mt19937 rand(rd());
    std::uniform_int_distribution<unsigned long long> dist(0, NUMELEM * 2);

    unsigned long long timeNthElement = 0;
    unsigned long long timeSort = 0;

    for (size_t j = 0; j < NUMITER; ++j)
    {
        for (size_t i = 0; i < NUMELEM; ++i)
        {
            unsigned long long val = dist(rand);
            vec1[i] = val;
            vec2[i] = val;
        }
        ULONGLONG t1 = GetTickCount64();
        std::sort(begin(vec1), end(vec1));
        ULONGLONG t2 = GetTickCount64();
        std::nth_element(begin(vec2), begin(vec2)+NUMELEM/2, end(vec2));
        ULONGLONG t3 = GetTickCount64();
        if (vec1[NUMELEM / 2] != vec2[NUMELEM / 2])
        {
            Sleep(0); // I put a breakpoint here but of course never caught it...
        }
        timeSort += t2 - t1;
        timeNthElement += t3 - t2;
    }

    std::cout << "timeSort = " << timeSort << std::endl;
    std::cout << "timeNthElement = " << timeNthElement << std::endl;
    return 0;
}
于 2020-08-27T10:25:39.700 回答