外部排序[编辑 | 编辑源代码]

介绍[编辑 | 编辑源代码]

外部排序（External Sorting）是一种用于处理大规模数据集的排序算法，当数据量太大无法全部加载到计算机内存（RAM）时使用。与内部排序（如快速排序、归并排序）不同，外部排序需要借助外部存储（如硬盘、SSD）进行数据的分块处理与合并。

典型应用场景包括：

数据库系统中对大型表进行排序
大数据分析中的日志处理
科学计算中对海量实验数据的排序

核心原理[编辑 | 编辑源代码]

外部排序通常采用多路归并排序（Multiway Merge Sort）策略，主要分为两个阶段：

1. 分块排序阶段：

  * 将大文件分割为能装入内存的小块（称为"runs"或"chunks"）
  * 对每个块使用内部排序算法（如快速排序）进行排序
  * 将排序后的块写回外部存储

2. 归并阶段：

  * 从已排序的块中读取部分数据到内存
  * 使用优先队列（如最小堆）进行k路归并
  * 将归并结果写入最终输出文件

算法实现[编辑 | 编辑源代码]

以下是Python伪代码实现外部排序的核心逻辑：

import heapq

def external_sort(input_file, output_file, chunk_size=100000):
    # 阶段1：分块排序
    temp_files = []
    with open(input_file, 'r') as f:
        chunk = []
        for line in f:
            chunk.append(int(line.strip()))
            if len(chunk) >= chunk_size:
                chunk.sort()  # 内部排序
                temp_file = write_temp_file(chunk)
                temp_files.append(temp_file)
                chunk = []
        # 处理剩余数据
        if chunk:
            chunk.sort()
            temp_file = write_temp_file(chunk)
            temp_files.append(temp_file)
    
    # 阶段2：k路归并
    with open(output_file, 'w') as out_f:
        # 打开所有临时文件
        file_handles = [open(fname, 'r') for fname in temp_files]
        # 初始化优先队列
        heap = []
        for i, fh in enumerate(file_handles):
            line = fh.readline()
            if line:
                heapq.heappush(heap, (int(line.strip()), i))
        
        # 开始归并
        while heap:
            val, file_idx = heapq.heappop(heap)
            out_f.write(f"{val}\n")
            next_line = file_handles[file_idx].readline()
            if next_line:
                heapq.heappush(heap, (int(next_line.strip()), file_idx))
        
        # 清理临时文件
        for fh in file_handles:
            fh.close()
        for fname in temp_files:
            os.remove(fname)

def write_temp_file(data):
    temp_name = f"temp_{len(data)}_{hash(tuple(data))}.txt"
    with open(temp_name, 'w') as f:
        for num in data:
            f.write(f"{num}\n")
    return temp_name