我应该使用java集合排序()还是实现我自己的呢？

Question

我有一个数组，我需要按递增顺序排序这些值。数组中的可能值在1-9之间，会有很多重复的值。(fyi:我正在做一个sudoku解谜器，试图用回溯的方法从盒子开始解决这个难题。)

到我的矿井的第一个想法是使用Shell排序。

我进行了一些查找，发现java集合使用“修改的mergesort”(如果低子列表中的最高元素小于高子列表中的最低元素，则省略合并)。

因此，我想知道，如果我实现自己的排序算法，性能上的差异是否会很明显。

Answer 1

如果您只有9个可能的值，那么您可能需要计数排序 --基本思想是：

• 创建大小为9的计数数组。
• 迭代数组，并为每个元素在计数数组中增加相应的索引。
• 遍历计数数组并重新创建原始数组。

它的运行时间是O(n + 9) = O(n)，因为标准API排序的运行时间将是O(n log n)。

因此，这很可能比Java使用的基于比较的标准排序更快，但是只有基准测试才能确定地告诉您(它可能取决于数据的大小)。

通常，我建议您首先尝试使用标准的API排序函数()，看看它是否足够快--它实际上只是一行代码(除非您必须定义一个比较函数)，与创建您自己的排序函数的比较函数相比，已经做了相当多的工作，以确保它尽可能快，同时保持它的通用性。

如果这还不够快，请尝试找到并实现一种与您的数据工作良好的排序。例如：

• 插入排序在已经几乎排序的数据上工作得很好(尽管如果数据远没有排序的话，运行时间是非常糟糕的)。
• 如果您有数字数据，分布分类是值得考虑的。

正如注释中所指出的，(来自Java 8)也是一个值得考虑的选项，因为它是多线程的工作( sort不做，当然是相当大的努力做自己.有效地)。