如何在 Java 中利用数组实现简单的外部排序（External Sort）块读取与多路归并

如何在 Ja va 中利用数组实现简单的外部排序（External Sort）块读取与多路归并

直接用一个数组搞定真正的外部排序？这在Ja va里行不通。毕竟，外部排序处理的是远超内存容量的海量数据，单个数组的内存容量是硬性限制。不过，用数组来模拟外部排序的核心思想，却是完全可行的。关键在于理解：这里的数组，扮演的并非磁盘替代品，而是“内存中的一块缓冲区”或“一个已排序的有序段”。理解了这一点，再通过多路归并的魔法，就能将这些分散的有序段整合成全局有序的结果。

1. 分块读取与生成有序段（Runs）

想象一下，你面对一个超大的整数序列，比如从文件里源源不断读出来。内存一次装不下全部，怎么办？答案是分而治之。设定一个MAX_BUFFER_SIZE，每次只加载这么多元素到内存。这时，数组就作为完美的缓冲区登场。

• 首先，打开输入源（比如BufferedReader），分批将数据读入int[] buffer = new int[MAX_BUFFER_SIZE]。
• 这里有个细节：实际读入的数量可能小于缓冲区大小（比如读到文件末尾了），所以必须记录下有效的长度validLength。
• 接下来，对这部分有效数据调用Arrays.sort(buffer, 0, validLength)，一个新鲜出炉的有序段（run）就诞生了。
• 最后，这个run可以写入临时文件（例如run_0.tmp）存档，也可以直接作为一个int[]对象，暂存到List runs里，留待后续处理。

2. 构建最小堆实现 k-路归并

现在，手头有了k个已排序的数组（也就是k个runs），目标是把它们归并成一个全局升序的序列。这个场景下，PriorityQueue（优先级队列）模拟的最小堆就成了得力工具。不过，堆里的元素不能只是个简单的值，它还得“记住”自己来自哪个数组、当前位置在哪。

• 通常，我们会定义一个静态内部类：RunEntry { int value; int runIndex; int pos; }，用来封装这些信息。
• 初始化堆时，遍历每一个run，只要它不为空，就把它的第一个元素（runs.get(i)[0]）打包成RunEntry，放入堆中。
• 然后进入循环：弹出堆顶（当前最小值）并输出；紧接着，从这个元素所属的run里，取出下一个位置（pos+1）的新元素（如果还有的话），再次封装入堆。
• 如此往复，直到堆变空，归并大业便宣告完成。

3. 使用数组作为归并过程中的输出缓冲区

归并出来的结果，不一定非得一次性全塞进内存。更常见的做法是分块写出。这时，又一个数组派上用场了——一个固定大小的int[] outputBuffer，充当高效的中转站。

（此处可参考“Ja va免费学习笔记（深入）”以获取更系统的知识。）

• 设定一个BUFFER_FLUSH_SIZE。每当归并产生的元素数量达到这个阈值，就批量将它们写入目标文件，或者收集到最终的结果列表里。
• 这样做的好处是避免了频繁的I/O操作，只有输出缓冲区满了才“刷”一次数据。当然，循环结束后，别忘了把缓冲区里剩余的数据也“flush”干净。
• 如果最终结果的总量确实可以装入内存，那也可以选择直接归并到一个预先分配好的大数组（int[] result = new int[totalSize]）里，边归并边填入，一气呵成。

4. 完整流程示例（内存版，无磁盘 I/O）

为了更清晰地理解整个逻辑，我们来看一个纯内存版本的演示。假设现在有3个已经排好序的int[]数组：

int[][] runs = {
    {1, 7, 12},
    {3, 8, 10, 15},
    {2, 5, 9}
};
// → 归并后应得 [1,2,3,5,7,8,9,10,12,15]

整个过程的核心，就是利用PriorityQueue来管理每一路当前最小的候选元素。这里必须注意几个容易踩坑的细节：每个run的访问必须严格通过其自身的索引和位置游标，不能直接修改原数组；要小心游标越界检查；遇到空的run要果断跳过；同时要确保每次只从对应的run推入一个新元素到堆里，避免重复或遗漏；最后，准确预估总元素数量totalSize，这直接关系到结果数组的分配。

话说回来，在实际工程项目中，通常会结合RandomAccessFile或者NIO的MappedByteBuffer来管理临时文件。而在整个过程中，数组始终坚守着它的核心角色——高效、灵活的“内存工作窗口”。