问对少量元素进行排序

EN

让我们来看看排序网络。

以下是几个链接：

http://en.wikipedia.org/wiki/Sorting_network

http://www.cs.uky.edu/~lewis/essays/algorithms/sortnets/sort-net.html

Fastest sort of fixed length 6 int array

你是否对你的应用程序进行了profile，而这最终成为了一个瓶颈？或者你正试图过度优化？

Bubblesort也可以很好地工作。特别是，当您的数据已经排序时，它实际上是最优的，并且将优于任何教科书上的合并或堆排序。除非你给出了完整的约束条件(交换元素的成本、稳定性要求、就位或不就位...)没有人能完全回答这个问题。

无论如何，对于四个元素来说，如何实现高效的合并内联排序是相当明显的。

对于奇数(2的非幂)大小，我认为向后插入排序是一种常见的优化。看一看Javas排序实现。我相信它已经有了这么小的数组优化。你有没有检查过你将要调用的排序例程没有做过这种优化？

所有优化问题的答案都必须以警告开头，即您应该分析并仅优化瓶颈，因此:一定要这样做。

本着C/C++的精神，我现在将相信你已经这样做了，并回答了你提出的问题。

您可以通过迭代分析来确定问题的答案。

编写默认实现使用std lib排序的template <int N> inline void sort_n(int * list)。在您的代码中适当的时候使用此模板。然后为您还没有专门化的最小N个案例编写一个模板专门化。在写完这个专门化之后，分析一下你的程序，看看你是否获得了显著的性能提升。如果您获得了您认为显著的性能提升，请重复执行。一旦你写了一个专门化，但没有从中得到太多，就停止吧。