blocks|key|232148|text|std::sort对所有元素进行排序。std::nth_elenemt并非如此，它只是将第n个元素放在第n个位置，一边是更小或相等的元素，另一边是更大或相等的元素。如果你想找到第n个元素(很明显)，或者你想要n个最小或最大的元素，那么就使用它。完整的排序可以满足这些要求。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|232149|那么为什么不直接执行全排序并获取第n个元素呢？因为std::nth_element有O(N)复杂度的要求，而std::sort是O(Nlog(N))。std::sort不能满足std::nth_element的复杂度要求。如果您不需要对范围进行完整的排序，那么使用它是很有好处的。|232150|至于你的例子，当我在GCC+4.7上运行类似的代码时，我得到了预期的结果：|232151|++for+(+int+i+=+0;+i+<+10;+i%2B%2B+)
++++myvector.push_back(rand()%2532);+//+make+the+numbers+small

++cout+<<+myvector+<<+"\n";
//+nth_element+around+the+4th+element
++nth_element+(myvector.begin(),+myvector.begin()%2B4,+myvector.end());
++cout+<<+myvector+<<+"\n";
++std::sort(myvector.begin(),+myvector.end());
++cout+<<+myvector+<<+"\n";|code-block|syntax|javascript|232152|产生|232153|{+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+}
+++++++++++++++%5E|232154|其中我使用了定制的ostream+operator<<来打印结果。|232155|entityMap^0|0|9|J|G|0|P|G|1I|9|23|9|2G|G|0|0|0|0|0|9|I|0^^$0|@$1|2|3|4|5|6|7|W|8|@$9|X|A|Y|B|C]|$9|Z|A|10|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|11|8|@$9|12|A|13|B|C]|$9|14|A|15|B|C]|$9|16|A|17|B|C]|$9|18|A|19|B|C]]|D|@]|E|$]]|$1|H|3|I|5|6|7|1A|8|@]|D|@]|E|$]]|$1|J|3|K|5|L|7|1B|8|@]|D|@]|E|$M|N]]|$1|O|3|P|5|6|7|1C|8|@]|D|@]|E|$]]|$1|Q|3|R|5|L|7|1D|8|@]|D|@]|E|$M|N]]|$1|S|3|T|5|6|7|1E|8|@$9|1F|A|1G|B|C]]|D|@]|E|$]]|$1|U|3|-4|5|6|7|1H|8|@]|D|@]|E|$]]]|V|$]]

<code>std::sort</code> sorts all the elements. <code>std::nth_elenemt</code> doesn't. It just puts the nth element in the nth positions, with smaller or equal elements on one side and larger or equal elements on the other. It is used if you want to find the nth element (obviously) or if you want the n smallest or largest elements. A full sort satisfies these requirements.

So why not just perform a full sort and get the nth element? Because <code>std::nth_element</code> has the requirement of having O(N) complexity, whereas <code>std::sort</code> is O(Nlog(N)). <code>std::sort</code> cannot satisfy the complexity requirement of <code>std::nth_element</code>.
If you do not need complete sorting of the range, it is advantageous to use it.

As for your example, when I run similar code on GCC 4.7, I get the expected results:

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

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

produces

<pre><code>{ 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 }
 ^
</code></pre>

where I've used a custom made <code>ostream operator&lt;&lt;</code> to print out the results.

blocks|key|229818|text|对于std::nth_element来说，为了满足文档化的语义而对整个范围进行排序是完全有效的-但是，这样做将无法满足所需的复杂性(线性)。关键的一点是，它可能会这样做，但它不一定要这样做。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|229819|这意味着std::nth_element可以提早摆脱困境--一旦它可以判断出您的范围的n'th元素是什么，它就可以停止。例如，对于一个范围|229820|[9,3,6,2,1,7,8,5,4,0]|code-block|syntax|javascript|229821|要求它给出第四个元素可能会产生如下结果|229822|[2,0,1,3,8,5,6,9,7,4]|229823|列表是部分排序的，刚刚好到能够辨别出顺序中的第四个元素将是3。|229824|因此，如果你想回答“哪个数字是第四个最小的”或者“哪个是四个最小的”，那么std::nth_element就是你的朋友。|229825|如果您想要得到四个最小的数字的顺序，您可能想要考虑使用std::partial_sort。|229826|entityMap|0|LINK|mutability|MUTABLE|url|http://en.cppreference.com/w/cpp/algorithm/nth_element|1|http://en.cppreference.com/w/cpp/algorithm/partial_sort^0|2|G|2|G|0|0|4|G|17|4|0|0|0|0|T|1|0|11|G|0|R|H|R|H|1|0^^$0|@$1|2|3|4|5|6|7|16|8|@$9|17|A|18|B|C]]|D|@$9|19|A|1A|1|1B]]|E|$]]|$1|F|3|G|5|6|7|1C|8|@$9|1D|A|1E|B|C]|$9|1F|A|1G|B|C]]|D|@]|E|$]]|$1|H|3|I|5|J|7|1H|8|@]|D|@]|E|$K|L]]|$1|M|3|N|5|6|7|1I|8|@]|D|@]|E|$]]|$1|O|3|P|5|J|7|1J|8|@]|D|@]|E|$K|L]]|$1|Q|3|R|5|6|7|1K|8|@$9|1L|A|1M|B|C]]|D|@]|E|$]]|$1|S|3|T|5|6|7|1N|8|@$9|1O|A|1P|B|C]]|D|@]|E|$]]|$1|U|3|V|5|6|7|1Q|8|@$9|1R|A|1S|B|C]]|D|@$9|1T|A|1U|1|1V]]|E|$]]|$1|W|3|-4|5|6|7|1W|8|@]|D|@]|E|$]]]|X|$Y|$5|Z|10|11|E|$12|13]]|14|$5|Z|10|11|E|$12|15]]]]

It's perfectly valid for <a href="http://en.cppreference.com/w/cpp/algorithm/nth_element" rel="noreferrer"><code>std::nth_element</code></a> to sort the entire range for fulfilling the documented semantic - however, doing so will fail at meeting the required complexity (linear). The key point is that it may do so, but it doesn't have to.

This means that <code>std::nth_element</code> can bail out early - as soon as it can tell what the <code>n'th</code> element of your range is going to be, it can stop. For instance, for a range

<pre><code>[9,3,6,2,1,7,8,5,4,0]
</code></pre>

asking it to give you the fourth element may yield something like

<pre><code>[2,0,1,3,8,5,6,9,7,4]
</code></pre>

The list was partially sorted, just good enough to be able to tell that the fourth element in order will be <code>3</code>.

Hence, if you want to answer 'which number is the fourth-smallest' or 'which are the four smallest' numbers then <code>std::nth_element</code> is your friend.

If you want to get the four smallest numbers in order you may want to consider using <a href="http://en.cppreference.com/w/cpp/algorithm/partial_sort" rel="noreferrer"><code>std::partial_sort</code></a>.

blocks|key|3101875|text|std::nth_element的实现如下所示：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3101876|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
}|code-block|syntax|javascript|3101877|其中ISORT_MAX定义为32。|3101878|所以如果你的序列比32个元素短，它就会对它执行InsertionSort。因此，您的短序列是完全排序的。|3101879|entityMap^0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|M|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|N|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|O|8|@]|9|@]|A|$]]|$1|I|3|J|5|6|7|P|8|@]|9|@]|A|$]]|$1|K|3|-4|5|6|7|Q|8|@]|9|@]|A|$]]]|L|$]]

The implementation of std::nth_element looks as follows:

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

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

 _Insertion_sort(_First, _Last, _Pred); // sort any remainder
}
</code></pre>

where ISORT_MAX defined as 32.

So if your sequence is shoter than 32 elements it just performs InsertionSort on it.
Therefore your short sequence is full sorted.

blocks|key|230875|text|我比较了std::sort和std::nth_element的执行时间，当运行在大量随机的无符号长整型向量(512MB)上，并取其中的中间元素时。是的，我知道它是O(N+log(N))+vs+O(N)，不管怎样，我预计std::nth_element(mid)的速度大约是std::sort的两倍，因为它应该对大约一半的元素进行“排序”。结果让我有点惊讶，这就是为什么我要分享它们：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|230876|timeSort+=+217407+(msec)
timeNthElement+=+18218+(msec)|code-block|syntax|javascript|230877|std::sort大约比慢12倍|offset|length|style|BOLD|230878|下面是我使用的代码片段(它使用windows.h)：|230879|#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;+%2B%2Bj)
++++{
++++++++for+(size_t+i+=+0;+i+<+NUMELEM;+%2B%2Bi)
++++++++{
++++++++++++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)%2BNUMELEM/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+%2B=+t2+-+t1;
++++++++timeNthElement+%2B=+t3+-+t2;
++++}

++++std::cout+<<+"timeSort+=+"+<<+timeSort+<<+std::endl;
++++std::cout+<<+"timeNthElement+=+"+<<+timeNthElement+<<+std::endl;
++++return+0;
}|230880|entityMap^0|0|0|0|C|0|0|0^^$0|@$1|2|3|4|5|6|7|S|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|T|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|U|8|@$I|V|J|W|K|L]]|9|@]|A|$]]|$1|M|3|N|5|6|7|X|8|@]|9|@]|A|$]]|$1|O|3|P|5|D|7|Y|8|@]|9|@]|A|$E|F]]|$1|Q|3|-4|5|6|7|Z|8|@]|9|@]|A|$]]]|R|$]]

I have compared execution times of std::sort vs. std::nth_element when running on a large vectors (512MB) of random unsigned long long's and taking middle element of it. Yes, I know it is O(N log(N)) vs O(N), anyway somehow I expected std::nth_element(mid) to be about twice as fast as std::sort, as it should be interested in &quot;sorting&quot; about half of elements. Results surprised me a bit, that's why I'm sharing them:
<pre><code>timeSort = 217407 (msec)
timeNthElement = 18218 (msec)
</code></pre>
std::sort was about 12 times slower
Here is the piece of code I used (it is using windows.h) :
<pre><code>#include &lt;windows.h&gt;
#include &lt;string&gt;
#include &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;algorithm&gt;
#include &lt;iterator&gt;
#include &lt;random&gt;

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

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

 for (size_t j = 0; j &lt; NUMITER; ++j)
 {
 for (size_t i = 0; i &lt; 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 &lt;&lt; &quot;timeSort = &quot; &lt;&lt; timeSort &lt;&lt; std::endl;
 std::cout &lt;&lt; &quot;timeNthElement = &quot; &lt;&lt; timeNthElement &lt;&lt; std::endl;
 return 0;
}
</code></pre>

I've been looking at the std::nth_element algorithm which apparently:

<blockquote>
 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.
</blockquote>

However, with my compiler, running the following:

<pre><code> vector&lt;int&gt; myvector;
 srand(GetTickCount());

 // set some values:
 for ( int i = 0; i &lt; 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 &lt;&lt; " " &lt;&lt; *it;

 cout &lt;&lt; endl;
</code></pre>

Always returns a completely sorted list of integers in exactly the same way as std::sort does. Am I missing something? What is this algorithm useful for?

EDIT: Ok the following example using a much larger set shows that there is quite a difference:

<pre><code> vector&lt;int&gt; myvector;
 srand(GetTickCount());

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

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

 vector&lt;int&gt; copy = myvector;
 std::sort(myvector.begin(), myvector.end());

 cout &lt;&lt; (myvector == copy ? "true" : "false") &lt;&lt; endl;
</code></pre>

What's the practical difference between std::nth_element and std::sort?

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

我一直在研究std::nth_element算法，显然：重新排列范围[first，last)中的元素，使得结果第n个位置的元素是排序序列中该位置的元素，其前面的元素都不大于，后面的元素也都不小于它。它前面的元素和后面的元素都不保证是有序的。但是，使用我的编译器，运行以下命令： vector<int> myvect...

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

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

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

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

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