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

我们有一个客户端应用程序可以发送请求并接收int数据流（可能很大，但小于INT_MAX）。我们需要这样做：

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

所以如下我会写的方法：

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

的问题是，大array无法放入堆栈，将投入堆这降低了性能。如何在良好的性能方式重构它？

2017-10-20 St.Antario

如果数据不适合堆栈，我认为没有任何魔法可以使它合适 – Felk

@Felk是的，这就是为什么我要求以另一种方式来处理它。 –

你必须想出一个逻辑来将数据拆分成块，然后以某种方式处理块 - >用堆排序或其他东西 – Lino

独立的编程语言，整理大量数据的常用方法是如下：

一些优化的实现甚至对大致适合CPU高速缓存（例如timsort）的数据集执行插入排序或类似操作。

但是，由于数据确实适合RAM，因此Java的本机实现应该已经非常快了。如果它超出内存，或者你想限制内存使用量，你将不得不使用external sorting。但是，这是肯定慢，因为它去磁盘

2017-10-20 13:25:28 Felk

我已经使用外部排序技术对60GB数据进行排序。该文件为.csv格式，每行都包含两个十进制数字。实施起来并不难。我把这个文件分成每块64MB（临时文件）。然后我自己排序每个块。休息是合并排序到最终文件。它确实有效，总共花费了大约32分钟。调整块大小也会影响时间。 –

那么....如果他们要求你如何如何排序数据和不提供数据进行排序，然后Arrays.sort（）应该工作精细。但是，排序的最佳方式取决于数据，Quicksort和Insertion是排序整数数组中速度最快的，但对于浮点数组，您需要专门的排序方法。

^就是说的排序算法许多接受的方式，用数学的缺点每一个完整列表。

2017-10-20 16:45:32 Brenann

回答