Ste*_* Lu 4 c c++ sorting optimization
我经常发现自己处于一种我想要排序少量元素的情况.通过小,我的意思是3或4.我可能正确地认为,对于这样小的问题集,我会想要使用某种类型的显式或直接方法而不是调用sort函数.2是微不足道的,3个元素仍然非常简单,但超过4项左右,我开始更喜欢只运行插入排序的简单性.
我可以期望编码多少元素inline void sort_n(int *list)？4？5？6？
在本主题中,仅使用3个元素对int数组进行排序,有两种解决方案可以对提供的3个元素进行排序.一个有更多的比较,而另一个最小化比较,但更复杂.在一个现代化的建筑上,它会在速度上脱颖而出吗？
你个人资料您的应用程序,这变成是一个瓶颈？或者你想过度优化？
Bubblesort也可以很好地工作.特别是,当您的数据已经排序时,它实际上是最佳的,并将击败任何教科书合并或堆排序.除非你给出完全的约束(交换元素的成本,稳定性要求,就地与否......)没有人可以完全回答这个问题.
无论如何,对于四个元素,如何实现内联的高效合并排序是相当明显的.
对于奇数(2的非幂)大小,我相信向后插入排序是一种常见的优化.看看Javas排序实现.我相信它已经有如此小的阵列优化.您是否检查过您调用的排序例程是否尚未进行此类优化？
优化问题的所有答案都必须以警告开头，即您应该分析并仅优化瓶颈，因此：请务必这样做。
本着 C/C++ 的精神，我现在相信您已经这样做并回答了您提出的问题。
您可以通过迭代分析来确定问题的答案。
写入template <int N> inline void sort_n(int * list)其默认实现使用 std lib 排序。只要在代码中合适，就可以使用此模板。然后为您还没有专门化的最小 N 情况编写模板专门化。编写此专业化后，分析您的程序并查看您是否取得了显着的性能提升。如果您认为性能获得显着提升，请重复。一旦你写了一个专业并且没有从中得到什么，就停下来。