C++ 外部排序实现详解 - 大数据排序解决方案 - 常规

外部排序是一种针对大数据量无法在内存中进行排序的情况下，将数据分批读入内存进行排序，再将排序后的数据写回硬盘的排序算法。下面是一个用 C++ 实现的外部排序示例：

首先，我们需要将原始数据分成若干个子文件，每个文件大小不超过内存容量。这里假设我们有一个名为'input.txt'的文件，每行包含一个整数，我们可以使用以下代码将其分割成多个子文件。

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX_MEMORY_SIZE = 1000000; // 内存大小
const string INPUT_FILE = "input.txt"; // 原始数据文件
const string OUTPUT_FILE_PREFIX = "output_"; // 子文件前缀

int main()
{
    ifstream fin(INPUT_FILE);
    if (!fin)
    {
        cerr << "Failed to open input file!" << endl;
        return 1;
    }

    int num = 0;
    vector<int> data;
    while (fin >> num) // 读入数据
    {
        data.push_back(num);
        if (data.size() * sizeof(int) >= MAX_MEMORY_SIZE) // 内存已满，写入子文件
        {
            sort(data.begin(), data.end());
            string filename = OUTPUT_FILE_PREFIX + to_string(data[0]) + ".txt";
            ofstream fout(filename);
            if (!fout)
            {
                cerr << "Failed to open output file!" << endl;
                return 1;
            }
            for (int i = 0; i < data.size(); ++i)
                fout << data[i] << endl;
            data.clear();
        }
    }

    if (!data.empty()) // 处理剩余数据
    {
        sort(data.begin(), data.end());
        string filename = OUTPUT_FILE_PREFIX + to_string(data[0]) + ".txt";
        ofstream fout(filename);
        if (!fout)
        {
            cerr << "Failed to open output file!" << endl;
            return 1;
        }
        for (int i = 0; i < data.size(); ++i)
            fout << data[i] << endl;
        data.clear();
    }

    fin.close();
    return 0;
}

上述代码将原始数据按照首个数字大小分成多个子文件，并按照从小到大的顺序将数据写入每个子文件中。

接下来，我们需要将子文件中的数据进行归并排序，并将结果写回硬盘。这里我们采用归并排序的方式进行排序。首先，我们需要定义一个用于读取子文件数据的类：

class FileReader
{
public:
    FileReader(const string& filename) : m_fin(filename), m_num(0) {}
    bool readNext()
    {
        if (m_fin >> m_num)
            return true;
        else
            return false;
    }

    int getNum() const { return m_num; }

private:
    ifstream m_fin;
    int m_num;
};

然后，我们可以使用一个最小堆来进行归并排序。首先，我们需要定义一个辅助类用于表示堆中的元素：

class HeapNode
{
public:
    HeapNode(int num, int fileIndex) : m_num(num), m_fileIndex(fileIndex) {}

    int getNum() const { return m_num; }
    int getFileIndex() const { return m_fileIndex; }

private:
    int m_num;
    int m_fileIndex;
};

接下来，我们可以定义一个最小堆类：

class MinHeap
{
public:
    MinHeap(const vector<string>& filenames) : m_heap(), m_fileReaders()
    {
        m_heap.reserve(filenames.size());
        m_fileReaders.reserve(filenames.size());
        for (int i = 0; i < filenames.size(); ++i)
            m_fileReaders.emplace_back(filenames[i]);
    }

    void buildHeap()
    {
        m_heap.clear();
        for (int i = 0; i < m_fileReaders.size(); ++i)
        {
            if (m_fileReaders[i].readNext())
            {
                m_heap.emplace_back(m_fileReaders[i].getNum(), i);
                push_heap(m_heap.begin(), m_heap.end(), [](const HeapNode& a, const HeapNode& b) { return a.getNum() > b.getNum(); });
            }
        }
    }

    bool isEmpty() const { return m_heap.empty(); }

    int getTop() const { return m_heap[0].getNum(); }

    void popTop()
    {
        pop_heap(m_heap.begin(), m_heap.end(), [](const HeapNode& a, const HeapNode& b) { return a.getNum() > b.getNum(); });
        int fileIndex = m_heap.back().getFileIndex();
        m_heap.pop_back();
        if (m_fileReaders[fileIndex].readNext())
        {
            m_heap.emplace_back(m_fileReaders[fileIndex].getNum(), fileIndex);
            push_heap(m_heap.begin(), m_heap.end(), [](const HeapNode& a, const HeapNode& b) { return a.getNum() > b.getNum(); });
        }
    }

private:
    vector<HeapNode> m_heap;
    vector<FileReader> m_fileReaders;
};

最后，我们可以使用以上定义的类来进行外部排序，并将结果写入'output.txt'中：

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include "FileReader.h"
#include "MinHeap.h"
using namespace std;

const int MAX_MEMORY_SIZE = 1000000; // 内存大小
const string OUTPUT_FILE = "output.txt"; // 排序结果文件

int main()
{
    vector<string> filenames;
    for (char c = 'a'; c <= 'z'; ++c)
        filenames.emplace_back(OUTPUT_FILE_PREFIX + string(1, c) + ".txt");

    int numFiles = filenames.size();
    while (numFiles > 1)
    {
        int numNewFiles = (numFiles + MAX_MEMORY_SIZE / sizeof(int) - 1) / (MAX_MEMORY_SIZE / sizeof(int)); // 每次排序后生成的新文件数
        vector<string> newFilenames(numNewFiles);
        for (int i = 0; i < numNewFiles; ++i)
            newFilenames[i] = OUTPUT_FILE_PREFIX + to_string(i) + ".txt";

        int numFilesPerBatch = (numFiles + numNewFiles - 1) / numNewFiles; // 每批处理的文件数
        for (int i = 0; i < numNewFiles; ++i)
        {
            int start = i * numFilesPerBatch;
            int end = min((i + 1) * numFilesPerBatch, numFiles);
            vector<string> batchFilenames(filenames.begin() + start, filenames.begin() + end);

            MinHeap heap(batchFilenames);
            heap.buildHeap();

            ofstream fout(newFilenames[i]);
            if (!fout)
            {
                cerr << "Failed to open output file!" << endl;
                return 1;
            }

            while (!heap.isEmpty())
            {
                fout << heap.getTop() << endl;
                heap.popTop();
            }
        }

        filenames = newFilenames;
        numFiles = numNewFiles;
    }

    rename(filenames[0].c_str(), OUTPUT_FILE.c_str()); // 将最终结果文件重命名为output.txt

    return 0;
}

以上代码将分割后的子文件进行归并排序，并将排序后的结果写入'output.txt'文件中。