我有一个数组，需要按递增顺序对值进行排序。数组里面的可能取值在1-9之间，会有很多重复值。 (仅供引用:我正在研究数独解算器，并尝试使用回溯从最小可能性的盒子开始解决难题)
我的第一个想法是使用 Shell 排序。
我做了一些查找，发现 java 集合使用“修改后的合并排序”(如果低子列表中的最高元素小于高子列表中的最低元素，则合并被省略)。
所以我想知道如果我实现自己的排序算法，性能差异是否会很明显。
最佳答案
如果您只有 9 个可能的值，您可能需要 counting sort - 基本思想是:
创建一个大小为 9 的计数数组。
遍历数组并为每个元素递增 count 数组中的相应索引。
遍历计数数组并重新创建原始数组。
它的运行时间为 O(n + 9) = O(n)，而标准 API 排序的运行时间为 O(n log n )。
是的，这很可能比 Java API 使用的基于比较的标准排序更快，但只有基准测试才能确定(并且可能取决于数据的大小)。
一般来说，我建议您首先尝试使用标准 API 排序，看看它是否足够快 - 它实际上只有 1 行代码(除非您必须定义一个比较函数)，与创建您自己的排序函数的许多其他函数相比，已经付出了相当多的努力来确保它尽可能快，同时保持它的通用性。
如果这还不够快，请尝试找到并实现一种适合您的数据的排序方式。例如:
Insertion sort在几乎已排序的数据上运行良好(尽管如果数据远未排序，运行时间非常糟糕)。
Distribution sorts如果您有数字数据，则值得考虑。
如评论中所述，Arrays.parallelSort (from Java 8)也是一个值得考虑的选项，因为它对工作进行了多线程处理(sort 做不到，当然需要付出相当多的努力才能高效地完成自己的工作)。
关于java - 我应该使用 java collection sort() 还是实现我自己的？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/24067736/