Java 数组实现外部排序（External Sort）：分块读取与多路归并详解
能否仅用一个数组完成真正的外部排序？在 Java 中，直接处理超出内存容量的海量数据时，单个数组存在物理内存限制。然而，利用数组来模拟外部排序的核心算法流程是完全可行的。关键在于明确：此处的数组并非替代磁盘，而是作为“内存缓冲区”或“已排序数据块（有序段）”的载体。掌握这一概念后，通过高效的多路归并策略，即可将这些独立的有序段合并为最终的整体有序序列。
1. 分块读取与有序段（Runs）生成
假设需要处理一个超大型的整数文件，其数据量远超内存容量。解决方案是采用分块处理策略。首先定义一个缓冲区大小常量 MAX_BUFFER_SIZE，每次仅加载该容量的数据到内存。此时，数组便扮演了核心缓冲区的角色。
- 首先，打开数据输入源（例如使用 BufferedReader），循环将数据分批读入int[] buffer = new int[MAX_BUFFER_SIZE]。
- 需要注意：最后一次读取的数据量可能不足缓冲区大小（例如文件末尾），因此必须记录实际有效数据长度validLength。
- 随后，对这部分有效数据调用Arrays.sort(buffer, 0, validLength)进行快速排序，一个完整的有序段（Run）即生成完毕。
- 最后，可将此有序段写入临时文件（如 run_0.tmp）进行持久化存储，或直接将其作为 int[] 对象暂存至 List
2. 基于最小堆的 K-路归并实现
当获得K 个已排序的数组（即 K 个有序段）后，目标是将它们合并为一个全局有序的序列。在此场景下，使用 PriorityQueue（基于最小堆）是最高效的选择。但堆中元素需额外记录其来源信息。
- 通常定义一个静态内部类：RunEntry { int value; int runIndex; int pos; }，用于封装元素值、所属有序段索引及段内当前位置。
- 初始化堆时，遍历所有非空有序段，将每个段的第一个元素（runs.get(i)[0]）包装为 RunEntry 对象并加入堆中。
- 随后进入循环：弹出堆顶元素（当前最小值）并输出；接着从该元素所属的有序段中获取下一个位置（pos+1）的元素（如果存在），重新封装为 RunEntry 并入堆。
- 重复此过程直至堆为空，即完成所有有序段的归并。
3. 数组作为归并输出缓冲区
归并产生的最终结果不必一次性全部加载到内存。更优的方案是使用分块输出策略。此时，可以定义一个固定大小的int[] outputBuffer 作为高效的输出缓冲区。
（更多系统知识可参考“Java免费学习笔记（深入）”。）
- 设置一个缓冲区刷新阈值 BUFFER_FLUSH_SIZE。当归并产生的元素数量达到此阈值时，便将缓冲区内的数据批量写入目标文件或追加至最终结果列表。
- 此做法的优势在于大幅减少了 I/O 操作次数，仅在缓冲区满时才执行一次“刷写”动作。循环结束后，务必记得将缓冲区中剩余的数据也进行刷新处理。
- 如果确认最终数据总量可被内存容纳，也可直接归并至一个预先分配的大数组（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
在实际的工程项目中，通常会结合 RandomAccessFile 或 NIO 的 MappedByteBuffer 来高效管理临时文件。而在整个外部排序的模拟过程中，数组始终承担着高效、灵活的“内存工作窗口”这一核心角色。
