小数组( 32或64个元素以下)的快速稳定排序
人们普遍认为，对于足够小的数组，插入排序是最好的。例如，蒂姆塞德对最多64个元素的数组使用(二进制)插入排序；来自维基百科：
一些分而治之的算法，如快速排序和合并排序，通过递归地将列表划分为较小的子列表，然后排序。在实践中，这些算法的一个有用的优化是使用插入排序来排序小的子列表，因为插入排序优于这些更复杂的算法。插入排序具有优势的列表的大小因环境和实现的不同而不同，但通常在8-20个元素之间。
这是真的吗？还有更好的选择吗？
如果这在很大程度上取决于平台，我对.NET最感兴趣。
回答 3
Stack Overflow用户
发布于 2009-08-17 19:30:26
我发现这真的取决于比较函数需要做多少工作。就像我间接地对工作表中的行进行排序一样，每次比较都涉及取一行，然后比较可能的几个列，可能混合数字和字符串比较，结果可能会变慢。
另一方面，如果数组的长度很短，则取决于您需要每秒排序多少次，因为即使它相对于可能的长度比较慢，您也可能永远不会注意到其中的差别。
如果我有任何疑问，我只是编码一个合并排序，并与之一起进行。我的经验很糟糕，因为qsort不稳定，有时需要很长时间。手工编码的合并排序简单，可靠，而且足够快。
Stack Overflow用户
发布于 2015-08-25 21:42:13
没有比插入排序更快的O(n log )算法了。然而，有一些O(n^2)算法是竞争的。值得注意的是，选择排序并不是其中之一，尽管在掉期和移动价格昂贵的罕见情况下，选择排序是好的。泡沫的分类和变体也是非常糟糕的。
网络排序:一种排序算法，始终稳定，无分支。它有糟糕的总体规格，但没有分支意味着恒星的表现在最小的名单上。基本情况是：if(a<b) swap(a,b);
插入分批排序:在每个循环中，对2-4个元素排序，然后将它们插入到一起。这减少了移动次数，并与较长列表相比减少了25 %至37 %。总体效果是对大小范围从16到64的列表进行优化。
Stack Overflow用户
发布于 2009-08-14 08:48:44
因为.NET是一种不编译为原始机器代码的语言。我认为调用API函数(它确实使用本机代码)可能是最快的方法。
https://stackoverflow.com/questions/1276716
复制相似问题
腾讯云开发者
