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

Question

我一直在看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;

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你的朋友就是.

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

Answer 2

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.因此,您的短序列已完全排序.

Answer 3

std::sort排序所有元素.std::nth_elenemt没有.它只是将第n个元素放在第n个位置,一边是较小或相等的元素,另一边是较大或相等的元素.如果要查找第n个元素(显然)或者想要n个最小或最大元素,则使用它.完整的排序满足这些要求.

那么为什么不只是执行完整的排序并获得第n个元素？因为std::nth_element具有O(N)复杂度的要求,而std::sortO(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<<打印结果.