java - 选择一个好的排序算法

Question

Java 应用程序将大部分时间用于对一些键进行排序和删除重复项。

因此，必须选择适应的排序算法。

键是整数（大约 256 位但不一定），数组大小在 1000 到 100000 个键之间。

输入数组由连续的键组组成。这些组已经排序并且很小（大约 10 个键）。

数组示例（3 组，32 位键）：

排序和删除重复项后：

有什么难的吗？任何想法？任何链接？

谢谢

PS：在查看了包括合并排序、基数排序、qui 的许多变体在内的排序算法之后，我继续挖掘哈希图。

PPS：最后我分叉了 Java 遗留的合并排序，添加了过滤和排序组的概念。它提供了很大的加速。

score 5 · Accepted Answer

合并排序 ( http://en.wikipedia.org/wiki/Merge_sort )

由于您的输入数据是预先排序的，因此您可以抢占先机。您可以将每个列表中的第一个值输入到 PriorityQueue 中，取出最少的值，然后将该列表中的下一个值添加到队列中。重复。进行一些检查以到达终点。:-)

我敢肯定有更完整的详细信息的答案。

更多链接：

http://www.cs.washington.edu/education/courses/cse373/06sp/handouts/lecture08.pdf

N路合并算法

并且，我自己用相当完整的 Java 代码回答：

使用复杂比较合并多个排序的 csv 文件

score 1 · Accepted Answer

没有更多细节的最简单的解决方案是

您应该能够将所有行读入 TreeSet 并在最后打印出来。

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
TreeSet<String> sortedSet = new TreeSet<String>();
for(String line; (line = br.readLine()) != null;)
    sortedSet.add(line);
for (String s : sortedSet) 
    System.out.println(s);

score 0 · Accepted Answer

我建议您在此处使用 Collections.sort，因为这样可以处理重复项（如果您为数字创建 SET），并且排序时间复杂度为 O(nlogn)，这是它所能得到的。

如果您只有一组特定的数字，那么您可能想看看基数排序。

score 0 · Accepted Answer

如果您每次都对全新的数组进行排序，您可能会受益于快速排序或桶排序

如果您的数组是更新斐波那契堆（最有效，虽然复杂）、二项式堆或简单的二元堆。

score 0 · Accepted Answer

由于您的排序键是有限范围内的整数，因此您可以使用radix sort。基数排序具有线性时间复杂度，而更通用的基于比较的排序算法对 n 个项目进行排序的运行时间最短为 O(n log n)，这使得基数排序和类似的排序算法更适合大型数据集。

score 0 · Accepted Answer

您可以遍历所有元素并将它们全部放在一个Set. 具体来说，将所有元素放在 aTreeSet中，以便为您提供正确的排序。这也将自动删除重复项。您的代码实际上非常简单-

Set<int> sortedUniqueKeys = new TreeSet<int>(keys);

其中 keys 是未排序的重复整数键数组。所有排序/重复删除都在构造函数中完成，并且（可能）很快。

java - 选择一个好的排序算法

6 回答 6

Related

Reference