如何对一个大型整数数组进行排序？

Question

在面试中，我被问到了以下问题：

我们有一个客户端应用程序，可以发送请求并接收一个 int 类型的数据流（可能很大，但不超过 INT_MAX）。我们需要做到以下几点：

Int Data  ----> Our  ----> Sorted Int Data
Stream          App        Data Stream

所以我会将方法编写如下：

public int[] sort(int[] array){
   Arrays.sort(array);
   return array;
}

问题在于数组太大，无法放入栈中，只能放入堆中，这会降低性能。如何以高性能的方式进行重构？

- St.Antario

---

除非你能把整个int集合都存储在某个地方，否则我看没有简单的方法可以对整个集合进行排序。即使分块处理也会强制你检查所有先前的块。 - BigMike

@Lino 但他们最终仍然需要将整个东西重新排序，对吧？尽管初始分页确实可以提高排序本身的性能。 - Mena

你的问题不太清楚。你想要对一串数据进行排序吗？流媒体意味着连续输入数据。在下载所有 int 数据之前，你不能对 int 流进行排序。那么你的问题只是“如何快速对 int 数组进行排序”吗？ - DodgyCodeException

你看过parallelSort了吗？ - Juan Carlos Mendoza

我只看到一种需要编写高度定制方法的解决方案。例如，您可以将所有内容拆分为适合的部分，然后对每个较小的片段进行排序，并以类似于拉链的方式将它们排序后组合起来。但是，您需要避免再次放置大结果，可能需要使用自定义类来保持其拆分状态，该类看起来像一个ArrayList，但在内部管理多个数组。但我不知道排序的开销是否可以证明避免堆的必要性。 - Zabuzard

Answer 1

独立于编程语言，排序大量数据的通常方式如下：

• 仅对一部分数据进行排序
• 使用归并排序合并所有已排序的数据块。

有些优化实现甚至在数据集大致适合CPU缓存（例如timsort）的情况下执行插入排序或类似操作。

然而，由于数据适合RAM，Java的本机实现应该已经非常快了。如果超过RAM限制，或者想要限制RAM使用情况，则必须使用外部排序。但这肯定会更慢，因为它需要访问磁盘。

- Felk

---

我使用外部排序技术对60GB的数据进行了排序。文件格式为.csv，每行包含两个大十进制数。实现起来并不难。我将该文件分成64MB一块（临时文件）。然后对每个块进行排序。剩下的就是归并排序到最终文件。它确实有效，并且总共需要约32分钟。调整块大小也会影响时间。 - Erdi İzgi

Answer 2

好的...如果他们要求你“如何”对数据进行排序，但没有提供要排序的数据，则Arrays.sort()应该可以正常工作。然而，最好的排序方式取决于数据，对于整数数组，快速排序和插入排序是最快的，但对于浮点数数组，您需要一种专门的排序方法。

https://en.wikipedia.org/wiki/Sorting_algorithm

以上是许多可接受的排序算法列表，每种算法都有其数学上的缺陷。

- Brenann