blocks|key|1516720|text|Introsort考虑到了您的关注，并切换到短序列的插入排序实现。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1516721|由于您的STL已经提供了它，您可能应该使用它。|1516722|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|F|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|G|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|H|8|@]|9|@]|A|$]]]|E|$]]

Introsort takes your concern into account, and switches to an insertion sort implementation for short sequences.
Since your STL already provides it, you should probably use that.

blocks|key|429132|text|插入排序或选择排序对于小型数组(即少于10-20个元素)来说通常都更快。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|429133|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

Insertion sort or selection sort are both typically faster for small arrays (i.e., fewer than 10-20 elements).

blocks|key|312986|text|观看https://www.youtube.com/watch?v=FJJTYQYB1JQ|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|312987|简单的线性插入排序非常快。首先创建一个堆可以稍微改进它。|312988|遗憾的是，这个话题并没有与<=+15元素的硬编码解决方案进行比较。|312989|entityMap|0|LINK|mutability|MUTABLE|url|https://www.youtube.com/watch?v=FJJTYQYB1JQ^0|2|17|0|0|0|0^^$0|@$1|2|3|4|5|6|7|P|8|@]|9|@$A|Q|B|R|1|S]]|C|$]]|$1|D|3|E|5|6|7|T|8|@]|9|@]|C|$]]|$1|F|3|G|5|6|7|U|8|@]|9|@]|C|$]]|$1|H|3|-4|5|6|7|V|8|@]|9|@]|C|$]]]|I|$J|$5|K|L|M|C|$N|O]]]]

Watch <a href="https://www.youtube.com/watch?v=FJJTYQYB1JQ" rel="nofollow noreferrer">https://www.youtube.com/watch?v=FJJTYQYB1JQ</a>
A simple linear insertion sort is really fast. Making a heap first can improve it a bit.
Sadly the talk doesn't compare that against the hardcoded solutions for &lt;= 15 elements.

blocks|key|1516651|text|如果不知道什么是“任何东西”，就不可能知道最快的方法是什么。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1516652|以下是一套可能的假设：|1516653|除了元素是相似的以外，我们对元素结构没有任何了解。我们没有有效的方法将它们分组(对于基排序)，我们必须实现基于比较的排序，并且比较是以不透明的方式进行的。|unordered-list-item|1516654|我们没有关于输入的初始状态的信息；任何输入顺序都是相同的。|1516655|我们不需要关心这种情况是否稳定。|1516656|输入序列是一个简单的数组。访问元素是固定时间的，交换元素也是如此。此外，我们将纯粹根据预期的比较数量(而不是掉期、挂钟时间或其他任何事情)来衡量这一功能。|1516657|有了这组假设(可能还有一些其他集合)，针对少量元素的最佳算法将是手工构建的排序网络，并根据输入数组的确切长度量身定制。(它们总是执行相同数量的比较；有条件地“短路”这些算法是不可行的，因为“条件”将取决于检测已经部分排序的数据，而这些数据仍然需要比较。)|offset|length|1516658|对于一个网络排序的四个元素(在已知的-最优的五个比较中)，这看起来可能是(我没有测试这个)：|1516659|template<class+RandomIt,+class+Compare>
void+_compare_and_swap(RandomIt+first,+Compare+comp,+int+x,+int+y)+{
++++if+(comp(first[x],+first[y]))+{
++++++++auto+tmp+=+first[x];
++++++++arr[x]+=+arr[y];
++++++++arr[y]+=+tmp;
++++}
}

//+Assume+there+are+exactly+four+elements+available+at+the+`first`+iterator.
template<class+RandomIt,+class+Compare>
void+network_sort_4(RandomIt+first,+Compare+comp)+{
++++_compare_and_swap(2,+0);
++++_compare_and_swap(1,+3);
++++_compare_and_swap(0,+1);
++++_compare_and_swap(2,+3);
++++_compare_and_swap(1,+2);
}|code-block|syntax|javascript|1516660|当然，在现实世界中，我们会有不同的假设。对于少量的元素，使用实际数据(但仍然假设我们必须进行基于比较的排序)，将很难克服插入排序(或冒泡排序，这实际上是相同的事情)的简单实现，这些实现都经过了良好的优化。考虑到硬件级别的复杂性(例如，对流水线指令所采取的步骤，然后补偿分支错误预测)和软件级别(例如，执行交换的相对成本与执行比较的相对成本，以及对性能的常量因素分析的影响)，手工进行这些事情是不可行的。|1516661|entityMap|0|LINK|mutability|MUTABLE|url|https://en.wikipedia.org/wiki/Sorting_network^0|0|0|0|0|0|0|11|4|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|17|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|18|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|19|8|@]|9|@]|A|$]]|$1|G|3|H|5|F|7|1A|8|@]|9|@]|A|$]]|$1|I|3|J|5|F|7|1B|8|@]|9|@]|A|$]]|$1|K|3|L|5|F|7|1C|8|@]|9|@]|A|$]]|$1|M|3|N|5|6|7|1D|8|@]|9|@$O|1E|P|1F|1|1G]]|A|$]]|$1|Q|3|R|5|6|7|1H|8|@]|9|@]|A|$]]|$1|S|3|T|5|U|7|1I|8|@]|9|@]|A|$V|W]]|$1|X|3|Y|5|6|7|1J|8|@]|9|@]|A|$]]|$1|Z|3|-4|5|6|7|1K|8|@]|9|@]|A|$]]]|10|$11|$5|12|13|14|A|$15|16]]]]

It's impossible to know the fastest way to do anything without knowing exactly what the &quot;anything&quot; is.
Here is one possible set of assumptions:
<ul>
<li>We don't have any knowledge of the element structure except that elements are comparable. We have no useful way to group them into bins (for radix sort), we must implement a comparison-based sort, and comparison takes place in an opaque manner.</li>
<li>We have no information about the initial state of the input; any input order is equally likely.</li>
<li>We don't have to care about whether the sort is stable.</li>
<li>The input sequence is a simple array. Accessing elements is constant-time, as is swapping them. Furthermore, we will benchmark the function purely according to the expected number of comparisons - not number of swaps, wall-clock time or anything else.</li>
</ul>
With that set of assumptions (and possibly some other sets), the best algorithms for small numbers of elements will be hand-crafted <a href="https://en.wikipedia.org/wiki/Sorting_network" rel="nofollow noreferrer">sorting networks</a>, tailored to the exact length of the input array. (These always perform the same number of comparisons; it isn't feasible to &quot;short-circuit&quot; these algorithms conditionally because the &quot;conditions&quot; would depend on detecting data that is already partially sorted, which still requires comparisons.)
For a network sorting four elements (in the known-optimal five comparisons), this might look like (I did not test this):
<pre><code>template&lt;class RandomIt, class Compare&gt;
void _compare_and_swap(RandomIt first, Compare comp, int x, int y) {
 if (comp(first[x], first[y])) {
 auto tmp = first[x];
 arr[x] = arr[y];
 arr[y] = tmp;
 }
}

// Assume there are exactly four elements available at the `first` iterator.
template&lt;class RandomIt, class Compare&gt;
void network_sort_4(RandomIt first, Compare comp) {
 _compare_and_swap(2, 0);
 _compare_and_swap(1, 3);
 _compare_and_swap(0, 1);
 _compare_and_swap(2, 3);
 _compare_and_swap(1, 2);
}
</code></pre>
<hr />
In real-world environments, of course, we will have different assumptions. For small numbers of elements, with real data (but still assuming we must do comparison-based sorts) it will be difficult to beat naive implementations of insertion sort (or bubble sort, which is effectively the same thing) that have been compiled with good optimizations. It's really not feasible to reason about these things by hand, considering both the complexity of the hardware level (e.g. the steps it takes to pipeline instructions and then compensate for branch mis-predictions) and the software level (e.g. the relative cost of performing the swap vs. performing the comparison, and the effect that has on the constant-factor analysis of performance).

In the critical path of my program, I need to sort an array (specifically, a C++ std::vector&lt;int64_t&gt;, using the gnu c++ standard libray). I am using the standard library provided sorting algorithm (std::sort), which in this case is introsort.
I was curious about how well this algorithm performs, and when doing some research on various sorting algorithms different standard and third party libraries use, almost all of them care about cases where 'n' tends to be the dominant factor.
In my specific case though, 'n' is going to be on the order of 2-20 elements. So the constant factors could actually be dominant. And things like cache effects might be very different when the entire array we are sorting fits into a couple of cache lines.
What are the best sorting algorithms for cases like this where the constant factors likely overwhelm the asymptotic factors? And do there exist any vetted C++ implementations of these algorithms?

What are the best sorting algorithms when 'n' is very small?

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

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

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

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

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

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

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

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云AI代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

功能1上新10个字符

功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符。

功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符。

功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符

功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符

功能4上新

文章&问答评论现已支持表情

全新交互，全新视觉，新增快捷键、悬浮工具栏、高亮块等功能并同时优化现有功能，全面提升创作效率和体验

社区富文本编辑器全新改版！诚邀体验～ 

精选全网热门MCP server，让你的AI更好用 🚀

💥开发者 MCP广场重磅上线！

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

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

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

社区新版编辑器体验调研

在我的程序的关键路径中，我需要对数组进行排序(特别是C++ std::vector<int64_t>，使用gnu c++标准libray)。我使用的是标准库提供的排序算法(std::sort)，在本例中是内向排序。我对这个算法的性能很好奇，在对不同标准和第三方库使用的各种排序算法进行研究时，几乎所有这些算法都关心“n”往往是主导因素的情况。在我的具体情况下，'n‘将在2-20个元素的顺序上。所以常

问当'n‘很小时，最好的排序算法是什么？
EN

回答 4

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问当'n‘很小时，最好的排序算法是什么？EN

回答 4

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问当'n‘很小时，最好的排序算法是什么？
EN