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

Question

我有一个数组,我需要按递增顺序对值进行排序.数组内部的可能值是1-9之间,会有很多重复值.(fyi:我正在研究一个数独求解器并尝试用最不可能的方法从盒子开始解决这个难题)

我的第一个想法是使用Shell Sort.

我做了一些查找,我发现java集合使用"modified mergesort"(如果低子列表中的最高元素小于high子列表中的最低元素,则省略合并).

因此,如果我实现自己的排序算法,我想知道性能的差异是否会引人注意.

Answer 1

如果您只有9个可能的值,您可能需要计算排序 - 基本思路是:

• 创建一个大小为9的计数数组.

• 遍历数组并递增每个元素的count数组中的相应索引.

• 遍历count数组并重新创建原始数组.

这将是O(n + 9) = O(n)运行时间,标准API排序的运行时间O(n log n).

所以,是的,这很可能比Java API使用的基于标准比较的排序更快,但只有基准测试才能确定(并且它可能取决于数据的大小).

一般来说,我建议您首先尝试使用标准API排序,看看它是否足够快 - 它只是一行代码(除非您必须定义比较函数),相比之下还有更多创建自己的排序功能,并确保尽可能快地完成相当多的努力,同时保持通用性.

如果这还不够快,请尝试查找并实现一种适合您的数据的排序.例如:

• 插入排序适用于已经几乎排序的数据(尽管如果数据远离排序,运行时间非常糟糕).

• 如果您有数字数据,则需要考虑分布排序.

正如评论中所指出的那样Arrays.parallelSort(来自Java 8)也是一个值得考虑的选择,因为它可以多线程工作(sort不能做到这一点,并且当然有效地做了很多努力......).