小型收藏品的最快排序

Question

很多时候，我不得不对大量的小列表、数组进行排序。我很少需要对大数组进行排序。这是排序最快的排序算法：

• arrays
• (array)lists

这些类型的大小为8-15个元素：

来自10-40个字符的

• integer
• string

我列出了元素类型，因为有些算法会做更多的比较操作和更少的交换操作。

我正在考虑合并排序，快速排序，插入排序和Shell排序(2^k-1增量).

Answer 1

Arrays.sort(..) / Collections.sort(..)将为你做出那个决定。

例如，openjdk-7 implementation of Arrays.sort(..)有INSERTION_SORT_THRESHOLD = 47 -它对那些元素少于47个的人使用插入排序。

Answer 2

除非您能够证明这是一个瓶颈，否则内置的类型是可以的：

Collections.sort(myIntList);

Arrays.sort(myArray);

Answer 3

事实上，没有一个普遍的答案。除其他外，Java排序算法的性能将取决于比较操作的相对成本，以及(对于某些算法)输入的顺序。在列表的情况下，它也取决于列表实现类型。

但是@Bozho的建议是合理的，就像的评论一样。

随访

如果您认为性能差异对您的用例有很大影响，那么您应该掌握不同算法的一些实现，并使用应用程序需要处理的实际数据来测试它们。(如果您还没有这些数据，那么现在就开始优化应用程序还为时过早，因为排序性能将取决于实际数据。)

简而言之，你需要自己做基准测试。