外部排序（External Sorting）

1. 什么是外部排序？

当数据太大，无法一次性加载到内存时，需要使用外部存储（如磁盘）进行排序，称为外部排序。

2. 外部排序的核心思想

分块排序（分段排序）：先将大文件分成多个可以放入内存的小块，每个小块单独排序后存入外存。
归并排序（合并排序）：再将这些已排序的小块进行多路归并，最终得到一个完整的有序文件。

常见外部排序方法：

多路归并排序（Multi-way Merge Sort）（最常用）
置换-选择排序（Replacement Selection）

多路归并排序（Multi-way Merge Sort）

原理

第一步：分块排序
- 把大数据文件切成多个小块，每个小块能放入内存。
- 在内存中对每个小块进行排序（可用快速排序或归并排序）。
- 排序后的小块写回外存（磁盘）。
第二步：多路归并
- 采用k路归并方法，将多个已排序的小块合并为一个大文件。
- 维护一个最小堆（堆排序）来找出当前所有块中的最小元素，逐步写入最终的输出文件。

代码实现

由于无法直接操作超大数据，这里用多个小文件模拟外部数据，并使用多路归并排序进行合并。

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

const int CHUNK_SIZE = 5; // 内存能容纳的最大元素数，模拟有限内存

// 生成大文件
void generateLargeFile(const string& filename, int numElements) {
    ofstream outFile(filename);
    if (!outFile) {
        cerr << "无法创建文件！" << endl;
        return;
    }

    srand(time(0));
    for (int i = 0; i < numElements; i++) {
        outFile << rand() % 100 << endl; // 生成0~99之间的随机数
    }
    outFile.close();
}

// 读取大文件并分块排序
vector<string> splitAndSortChunks(const string& filename) {
    ifstream inFile(filename);
    vector<string> chunkFiles;
    vector<int> buffer;

    int chunkIndex = 0;
    while (true) {
        buffer.clear();
        int num;
        for (int i = 0; i < CHUNK_SIZE && inFile >> num; i++) {
            buffer.push_back(num);
        }

        if (buffer.empty()) break;

        // 对块进行排序
        sort(buffer.begin(), buffer.end());

        // 将排序后的数据写入小文件
        string chunkFilename = "chunk_" + to_string(chunkIndex++) + ".txt";
        chunkFiles.push_back(chunkFilename);
        ofstream outFile(chunkFilename);
        for (int num : buffer) {
            outFile << num << endl;
        }
        outFile.close();
    }

    inFile.close();
    return chunkFiles;
}

// 多路归并排序（最小堆）
void mergeSortedChunks(const vector<string>& chunkFiles, const string& outputFilename) {
    ofstream outFile(outputFilename);
    if (!outFile) {
        cerr << "无法创建输出文件！" << endl;
        return;
    }

    // 优先队列（最小堆），存放 {值, 文件索引}
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minHeap;
    vector<ifstream> inFiles(chunkFiles.size());

    // 打开所有小文件，并读取第一个数放入堆
    for (int i = 0; i < chunkFiles.size(); i++) {
        inFiles[i].open(chunkFiles[i]);
        int num;
        if (inFiles[i] >> num) {
            minHeap.push({num, i});
        }
    }

    // 归并排序
    while (!minHeap.empty()) {
        auto [value, fileIndex] = minHeap.top();
        minHeap.pop();

        outFile << value << endl; // 写入最终结果

        // 从同一文件读取下一个数
        int nextNum;
        if (inFiles[fileIndex] >> nextNum) {
            minHeap.push({nextNum, fileIndex});
        }
    }

    // 关闭所有文件
    for (auto& file : inFiles) file.close();
    outFile.close();
}

// **主函数**
int main() {
    string inputFile = "large_input.txt";
    string outputFile = "sorted_output.txt";
    
    // **生成大文件**
    generateLargeFile(inputFile, 20);

    // **第一步：分块排序**
    vector<string> chunkFiles = splitAndSortChunks(inputFile);

    // **第二步：多路归并**
    mergeSortedChunks(chunkFiles, outputFile);

    cout << "外部排序完成！已写入文件：" << outputFile << endl;
    return 0;
}

代码解析

generateLargeFile
- 生成一个包含 20 个随机数 的大文件（模拟超大数据）。
splitAndSortChunks
- 读取固定大小（CHUNK_SIZE）的数据块。
- 逐块排序后存入小文件（模拟内存受限）。
mergeSortedChunks
- 维护一个最小堆，用于多路归并。
- 每次从最小堆中取最小值，然后从该文件读取下一个值。
- 直到所有文件归并完成。

时间复杂度分析

分块排序：O(n log k)（k = 每块大小）
归并排序：O(n log m)（m = 块的数量）

整体时间复杂度：O(n log n)，与归并排序相同。

总结

外部排序步骤	方式
分块排序	将大文件分割成多个小块，每个块在内存中排序后存储到外存
归并排序	使用最小堆进行多路归并，合并多个有序块