blocks|key|182272|text|首先，您需要对应用程序进行一些分析，以确定是否值得花费时间进行这种优化。我怀疑这不会成为现实。标准库(或boost)函数几乎肯定是排序的最佳选择。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|182273|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|$]]

You'll need to do some profiling of your application first to determine if doing this optimization is worth your time. I suspect it will not be. The standard library (or boost) functions will almost certainly be your best bet for sorting.

blocks|key|183892|text|你是否对你的应用程序进行了profile，而这最终成为了一个瓶颈？或者你正试图过度优化？|type|unstyled|depth|inlineStyleRanges|offset|length|style|BOLD|entityRanges|data|183893|Bubblesort也可以很好地工作。特别是，当您的数据已经排序时，它实际上是最优的，并且将优于任何教科书上的合并或堆排序。除非你给出了完整的约束条件(交换元素的成本、稳定性要求、就位或不就位...)没有人能完全回答这个问题。|183894|无论如何，对于四个元素来说，如何实现高效的合并内联排序是相当明显的。|183895|对于奇数(2的非幂)大小，我认为向后插入排序是一种常见的优化。看一看Javas排序实现。我相信它已经有了这么小的数组优化。你有没有检查过你将要调用的排序例程没有做过这种优化？|183896|entityMap^0|D|7|0|0|0|0^^$0|@$1|2|3|4|5|6|7|N|8|@$9|O|A|P|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|Q|8|@]|D|@]|E|$]]|$1|H|3|I|5|6|7|R|8|@]|D|@]|E|$]]|$1|J|3|K|5|6|7|S|8|@]|D|@]|E|$]]|$1|L|3|-4|5|6|7|T|8|@]|D|@]|E|$]]]|M|$]]

Did you profile your application and this turn out to be a bottleneck? Or are you trying to overoptimize?

Bubblesort can work very well, too. In particular, when your data is already sorted, it actually is optimal and will beat any textbook merge or heap sort. Unless you give the full constraints (cost of swapping elements, stability requirements, in-place or not...) nobody can answer this fully.

Anyway, for four elements it is rather obvious how to implement an efficient merge sort inline.

For odd (non-power of 2) sizes I belive that backwards insertion sort is a common optimization. Have a look at Javas sorting implementation. I believe it has such a small array optimization already. Did you check that the sort routine you would have called doesn't already do this kind of optimizations?

blocks|key|182298|text|有人告诉我，标准库排序已经优化了小型n的用例--我从未尝试过验证它。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|182299|entityMap^0|I|1|0^^$0|@$1|2|3|4|5|6|7|H|8|@$9|I|A|J|B|C]]|D|@]|E|$]]|$1|F|3|-4|5|6|7|K|8|@]|D|@]|E|$]]]|G|$]]

I'm told that the standard library sorts have optimized cases for small <code>n</code> - I've never tried to verify it.

blocks|key|5557636|text|对于任何合理数量的项目，您将始终从显式编码比较中获得性能优势。然而，对如此少的项目进行排序所需的时间如此之少，以至于您使用什么方法几乎不重要。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|5557637|您不会获得任何性能优势的阈值是当您获得的代码太多，以至于它不再适合CPU缓存时，因此阈值的位置将根据您在哪个CPU上运行它而有所不同。|5557638|您还应该考虑如何测试这些代码。你拥有的代码越多，就越难验证它是不是没有bug。|5557639|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|H|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|I|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|J|8|@]|9|@]|A|$]]|$1|F|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|G|$]]

For any reasonable number of items, you will always get a performance benefit from coding up the comparisons explicitly. However, sorting so few items takes so little time that it rarely matters what method you use anyway.

The threshold where you won't get any performance benefit is when you get so much code that it won't fit in the CPU cache any more, so where the threshold is will differ depending on which CPU you are running it on.

You should also consider how you would test such code. The more code you have, the harder it will be to verify that it's bug free.

blocks|key|5557716|text|插入排序和冒泡排序通常用于小数据。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|5557717|我相信插入排序是首选，引用这两个维基百科文本：|5557718|5557719|快速排序实现对小于某个阈值的数组使用插入排序|blockquote|5557720|5557721|5557722|和：|5557723|CPU冒泡排序与现代|5557724|硬件的交互性也很差。它至少需要两倍于插入排序的写操作，两倍于高速缓存未命中的高速缓存未命中，以及渐近更多的分支误预测。Astrachan在Java中对字符串进行排序的实验表明，冒泡排序大约比插入排序慢5倍，比选择排序慢40%25。|5557725|5557726|5557727|一如既往，如果你真的很关心速度，你应该分析一下。|5557728|entityMap^0|0|0|0|0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|V|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|W|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|X|8|@]|9|@]|A|$]]|$1|E|3|F|5|G|7|Y|8|@]|9|@]|A|$]]|$1|H|3|-4|5|6|7|Z|8|@]|9|@]|A|$]]|$1|I|3|-4|5|6|7|10|8|@]|9|@]|A|$]]|$1|J|3|K|5|6|7|11|8|@]|9|@]|A|$]]|$1|L|3|M|5|6|7|12|8|@]|9|@]|A|$]]|$1|N|3|O|5|G|7|13|8|@]|9|@]|A|$]]|$1|P|3|-4|5|6|7|14|8|@]|9|@]|A|$]]|$1|Q|3|-4|5|6|7|15|8|@]|9|@]|A|$]]|$1|R|3|S|5|6|7|16|8|@]|9|@]|A|$]]|$1|T|3|-4|5|6|7|17|8|@]|9|@]|A|$]]]|U|$]]

Insertion sort and bubble sort are generally used for small data.

I believe insertion sort is preferred, citing these 2 wikipedia texts:

<blockquote>
 quicksort implementations use insertion sort for arrays smaller than a certain threshold
</blockquote>

And:

<blockquote>
 Bubble sort also interacts poorly with modern CPU hardware. It requires at least twice as many writes as insertion sort, twice as many cache misses, and asymptotically more branch mispredictions. Experiments by Astrachan sorting strings in Java show bubble sort to be roughly 5 times slower than insertion sort and 40% slower than selection sort.
</blockquote>

As always, you should profile if you're really concerned with the speed.

blocks|key|1200317|text|所有优化问题的答案都必须以警告开头，即您应该分析并仅优化瓶颈，因此:一定要这样做。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1200318|本着C/C%2B%2B的精神，我现在将相信你已经这样做了，并回答了你提出的问题。|1200319|您可以通过迭代分析来确定问题的答案。|1200320|编写默认实现使用std+lib排序的template+<int+N>+inline+void+sort_n(int+*+list)。在您的代码中适当的时候使用此模板。然后为您还没有专门化的最小N个案例编写一个模板专门化。在写完这个专门化之后，分析一下你的程序，看看你是否获得了显著的性能提升。如果您获得了您认为显著的性能提升，请重复执行。一旦你写了一个专门化，但没有从中得到太多，就停止吧。|offset|length|style|CODE|1200321|entityMap^0|0|0|0|I|1B|0^^$0|@$1|2|3|4|5|6|7|N|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|O|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|P|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|Q|8|@$H|R|I|S|J|K]]|9|@]|A|$]]|$1|L|3|-4|5|6|7|T|8|@]|9|@]|A|$]]]|M|$]]

All answers to optimization questions must be prefaced by the warning that you should profile and only optimize bottlenecks, so: be sure to do that.

In the spirit of C/C++ I will now trust you to have done so and answer the question you have asked.

You determine the answer to your question by iteratively profiling.

Write <code>template &lt;int N&gt; inline void sort_n(int * list)</code> whose default implementation uses an std lib sort. Use this template whenever appropriate in your code. Then write a template specializations for the smallest N case for which you do not already have a specialization. After writing this specialization, profile your program and see if you made a significant performance gain. If you make a performance gain which you judge significant, repeat. Once you write a specialization and don't get much out of it, stop.

blocks|key|3942581|text|让我们来看看排序网络。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3942582|以下是几个链接：|3942583|http://en.wikipedia.org/wiki/Sorting_network|offset|length|3942584|http://www.cs.uky.edu/~lewis/essays/algorithms/sortnets/sort-net.html|3942585|Fastest+sort+of+fixed+length+6+int+array|3942586|entityMap|0|LINK|mutability|MUTABLE|url|1|2|https://stackoverflow.com/questions/2786899/fastest-sort-of-fixed-length-6-int-array^0|0|0|0|18|0|0|0|1X|1|0|0|14|2|0^^$0|@$1|2|3|4|5|6|7|V|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|W|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|X|8|@]|9|@$F|Y|G|Z|1|10]]|A|$]]|$1|H|3|I|5|6|7|11|8|@]|9|@$F|12|G|13|1|14]]|A|$]]|$1|J|3|K|5|6|7|15|8|@]|9|@$F|16|G|17|1|18]]|A|$]]|$1|L|3|-4|5|6|7|19|8|@]|9|@]|A|$]]]|M|$N|$5|O|P|Q|A|$R|E]]|S|$5|O|P|Q|A|$R|I]]|T|$5|O|P|Q|A|$R|U]]]]

Have a look at sorting networks.

A few links: 
<a href="http://en.wikipedia.org/wiki/Sorting_network" rel="nofollow noreferrer">http://en.wikipedia.org/wiki/Sorting_network</a> 
<a href="http://www.cs.uky.edu/~lewis/essays/algorithms/sortnets/sort-net.html" rel="nofollow noreferrer">http://www.cs.uky.edu/~lewis/essays/algorithms/sortnets/sort-net.html</a> 
<a href="https://stackoverflow.com/questions/2786899/fastest-sort-of-fixed-length-6-int-array">Fastest sort of fixed length 6 int array</a>

I am often finding myself in a situation where I want to sort a small number of elements. By small, I mean 3 or 4. I am probably correct in thinking that with such small problem sets I would want to use some type of explicit or direct method rather than invoking a sort function. 2 is trivial, 3 elements is still pretty simple but above 4 items or so and I'm starting to prefer the simplicity of just running insertion sort. 

Up to how many elements can I expect a benefit to coding up a <code>inline void sort_n(int *list)</code>? 4? 5? 6? 

In this topic, <a href="https://stackoverflow.com/questions/4793251/sorting-int-array-with-only-3-elements">sorting int array with only 3 elements</a>, there are two solutions for sorting 3 elements provided. One has more comparisons while the other minimizes comparisons but is more complicated. On a modern architecture, which would come out on top for speed?

Sorting small numbers of elements

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

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

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

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

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

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

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

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

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

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

我经常发现自己处于一种需要对少量元素进行排序的情况。小，我的意思是3或4。我的想法可能是正确的，对于这么小的问题集，我想要使用某种类型的显式或直接方法，而不是调用排序函数。2是微不足道的，3个元素仍然很简单，但超过4个项目，我开始喜欢简单的只是运行插入排序。编码一个inline void sort_n(int *lis...

问对少量元素进行排序
EN

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问对少量元素进行排序EN