海量數據排序：如何用 1MB 內存給 10^7 個整數的磁盤文件排序

編輯：關於C語言

前言：從面試題到編程藝術

經過深思熟慮，本系列正式更名為「程序員編程藝術」（TAOPP）。改名緣由三點：一、服務面試非最終目的；二、將解題過程視為藝術提煉；三、藝術提煉雖難，吾輩樂意接受挑戰。本系列分三部分：程序設計實戰、經典算法深度剖析、編碼素養與規範。期許能如《計算機程序設計藝術》（TAOCP）般出卷，為「何謂編程藝術」給出完整答覆。

問題描述

輸入：一個最多含有 n = 10^7 個不重複正整數的文件，每個數 ≤ n。
輸出：按升序輸出所有整數。
限制：內存 ≤ 1 MB，磁盤空間充足，運行時間 < 5 分鐘（10 秒為佳）。

逐步分析與解法演進

❌ 歸並排序？內存不夠

外部歸並排序需要較大內存作為緩衝區，1 MB 顯然無法容納 10^7 個整數（約 40 MB），故不可行。

✅ 位圖法—— 利用數據特性的巧妙方案

題目三大特性直指位圖：

數據範圍有限（0 ~ 10^7）
無重複
純整數，無附屬數據

核心思想：用一個 10^7 位（約 1.25 MB）的位向量，第 i 位為 1 表示整數 i 存在。但 1.25 MB 略超 1 MB 限制，故採用兩趟掃描：

第一趟處理 0 ~ 4,999,999（500 萬位 ≈ 0.625 MB）
第二趟處理 5,000,000 ~ 9,999,999（同樣位圖復用）

三步走流程

初始化：位圖全置 0
建立集合：讀入文件，對應位置 1
輸出有序結果：掃描位圖，位為 1 輸出索引值

偽代碼

// 位圖排序偽代碼
for i = 0 to n: bit[i] = 0
for each i in input_file: bit[i] = 1
for i = 0 to n:
    if bit[i] == 1: write i to output_file

完整 C++ 實現（兩趟掃描）

#include <iostream>
#include <bitset>
#include <cassert>
#include <ctime>
#include <cstdio>

using namespace std;

const int MAX_EACH_SCAN = 5000000; // 500 萬位 ≈ 0.625 MB

int main() {
    clock_t begin = clock();
    bitset<MAX_EACH_SCAN> bit_map;
    bit_map.reset();

    // --- 第一趟：處理 0 ~ 4,999,999 ---
    FILE *fp_in = fopen("data.txt", "r");
    assert(fp_in);
    int num;
    while (fscanf(fp_in, "%d", &num) != EOF) {
        if (num < MAX_EACH_SCAN) bit_map.set(num);
    }

    FILE *fp_out = fopen("sort.txt", "w");
    assert(fp_out);
    for (int i = 0; i < MAX_EACH_SCAN; ++i)
        if (bit_map.test(i)) fprintf(fp_out, "%d ", i);

    // --- 第二趟：處理 5,000,000 ~ 9,999,999 ---
    fseek(fp_in, 0, SEEK_SET); // 重置文件指針
    bit_map.reset();
    while (fscanf(fp_in, "%d", &num) != EOF) {
        if (num >= MAX_EACH_SCAN && num < 10000000) {
            bit_map.set(num - MAX_EACH_SCAN);
        }
    }
    for (int i = 0; i < MAX_EACH_SCAN; ++i)
        if (bit_map.test(i)) fprintf(fp_out, "%d ", i + MAX_EACH_SCAN);

    fclose(fp_in);
    fclose(fp_out);
    cout << "Time: " << (clock() - begin) / 1000.0 << "s" << endl;
    return 0;
}