java - 什么是对文件中数百万行整数进行排序的有效算法？

Question

在这种情况下，计数排序可能不起作用，因为 k 的值范围很大。

快速排序可以用于大数据吗？

Answer 1

数以百万计的元素通常不被视为大数据，所以我相信在这种情况下快速排序可以解决问题。

您可以通过将数组拆分为子数组q，将它们并行排序，然后使用k-way-merge合并生成的排序子数组来稍微固定它。

---

但是，如果您的数据非常庞大(10^9+) - 您需要考虑将作业分配给一组机器。

一种可扩展的方法是map-reduce。
本课程的第一张幻灯片讨论了使用 Map-Reduce 进行排序。

您可能想尝试名为Hadoop的 java 开源实现。

Answer 2

如果您的数据太大而无法放入主存储器，我会尝试的第一件事是STXXL，它是外部存储器算法的 STL 替代品。它应该比设置 Hadoop 集群更容易使用。它还具有多核并行性。

不过那是 C++，如果 Java 是硬性要求，您可能想在谷歌上搜索 Java 等价物。