【Java面试】10GB，1GB内存，如何排序？

🔍 一、外部排序步骤

1️⃣ 分块排序（分割阶段）

• 步骤：
  1. 将10GB文件分割为多个内存可容纳的小块（如每个块900MB，共约11块），避免内存溢出。
  2. 逐块读取到内存，使用高效排序算法（如Collections.sort()或Arrays.sort()）排序。
  3. 将排序后的块写入临时文件，生成11个有序子文件。
• 关键代码：

  List<File> splitAndSort(File input) throws IOException {
      List<File> chunks = new ArrayList<>();
      try (BufferedReader reader = new BufferedReader(new FileReader(input))) {
          List<String> buffer = new ArrayList<>();
          String line;
          while ((line = reader.readLine()) != null) {
              buffer.add(line);
              if (buffer.size() >= 10_000_000) { // 控制块大小
                  chunks.add(sortAndSave(buffer));
                  buffer.clear();
              }
          }
          if (!buffer.isEmpty()) chunks.add(sortAndSave(buffer));
      }
      return chunks;
  }
  
  File sortAndSave(List<String> data) throws IOException {
      Collections.sort(data); // 内部排序
      File tempFile = File.createTempFile("chunk", ".txt");
      tempFile.deleteOnExit();
      try (BufferedWriter writer = new BufferedWriter(new FileWriter(tempFile))) {
          for (String str : data) {
              writer.write(str);
              writer.newLine();
          }
      }
      return tempFile;
  }
  

2️⃣ 多路归并（合并阶段）

• 原理：使用最小堆（PriorityQueue）合并有序子文件，减少磁盘IO次数。
• 优化：
  • 缓冲区管理：为每个子文件分配约100MB缓冲区，预读数据到内存。
  • 堆优化：堆中存储每个文件的当前最小元素，弹出最小值后补充新元素。
• 关键代码：

  void mergeFiles(List<File> chunks, File output) throws IOException {
      PriorityQueue<BufferedLine> minHeap = new PriorityQueue<>();
      List<BufferedReader> readers = new ArrayList<>();
      
      // 初始化堆和读取器
      for (File file : chunks) {
          BufferedReader reader = new BufferedReader(new FileReader(file));
          readers.add(reader);
          String line = reader.readLine();
          if (line != null) minHeap.add(new BufferedLine(line, reader));
      }
  
      try (BufferedWriter writer = new BufferedWriter(new FileWriter(output))) {
          while (!minHeap.isEmpty()) {
              BufferedLine min = minHeap.poll();
              writer.write(min.line.replaceAll("\\d+$", "")); // 删除行尾序号
              writer.newLine();
              
              String nextLine = min.reader.readLine();
              if (nextLine != null) minHeap.add(new BufferedLine(nextLine, min.reader));
          }
      }
      
      // 关闭所有读取器
      for (BufferedReader reader : readers) reader.close();
  }
  
  class BufferedLine implements Comparable<BufferedLine> {
      String line;
      BufferedReader reader;
      public BufferedLine(String line, BufferedReader reader) {
          this.line = line; this.reader = reader;
      }
      @Override
      public int compareTo(BufferedLine o) {
          return this.line.compareTo(o.line); // 按字符串排序
      }
  }
  

🚀 二、优化策略

1. 减少IO开销：

   • 增大缓冲区（如100MB/文件），减少磁盘读取次数。
   • 使用BufferedReader和BufferedWriter加速读写]。

2. 动态分块：

   • 根据数据特征调整分块策略，若数据分布均匀可用桶排序（如按数值范围分桶）。

3. 归并路数控制：

   • 内存限制下，归并路数k需满足：k * 缓冲区大小 ≤ 1GB。例如11个文件需每个缓冲区≤90MB。

4. 资源清理：

   • 临时文件用File.deleteOnExit()自动删除。

💎 总结

• 核心流程：分块 → 内存排序 → 多路归并（最小堆）→ 输出时删除序号。
• 关键点：
  • 内存管理：分块大小需预留排序空间（如900MB/块）。
  • 性能优化：缓冲区 + 最小堆减少IO，正则表达式高效去序号。
• 适用场景：海量数据排序（日志处理、数据库操作等）。

此方案兼顾功能性（排序+数据清洗）与效率（O(n log n)时间复杂度），是Java面试中考察分布式处理能力的典型解法。