外排序置换选择排序c++完整代码

以下是外排序置换选择排序的 C++ 完整代码：

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

using namespace std;

// 外排序置换选择排序函数
void externalSort(string inputFile, string outputFile, int blockSize) {
    // 打开输入文件
    ifstream in(inputFile, ios::binary);

    // 获取文件大小
    in.seekg(0, in.end);
    long long fileSize = in.tellg();
    in.seekg(0, in.beg);

    // 计算每个块可以容纳的数据量
    int numBlocks = fileSize / blockSize;
    int lastBlockSize = fileSize - numBlocks * blockSize;
    if (lastBlockSize > 0) {
        numBlocks++;
    }

    // 从文件读取数据并将其分块
    vector<int> buffer(blockSize / sizeof(int));
    for (int i = 0; i < numBlocks; i++) {
        // 读取数据块
        if (i == numBlocks - 1 && lastBlockSize > 0) {
            buffer.resize(lastBlockSize / sizeof(int));
        }
        in.read((char*)&buffer[0], buffer.size() * sizeof(int));
        int numElements = in.gcount() / sizeof(int);

        // 对数据块进行排序
        sort(buffer.begin(), buffer.begin() + numElements);

        // 将排好序的数据块写入临时文件
        string tempFilename = "temp_" + to_string(i) + ".dat";
        ofstream tempOut(tempFilename, ios::binary);
        tempOut.write((char*)&buffer[0], numElements * sizeof(int));
        tempOut.close();
    }
    in.close();

    // 打开临时文件
    vector<ifstream*> tempFiles(numBlocks);
    for (int i = 0; i < numBlocks; i++) {
        string tempFilename = "temp_" + to_string(i) + ".dat";
        tempFiles[i] = new ifstream(tempFilename, ios::binary);
    }

    // 打开输出文件
    ofstream out(outputFile, ios::binary);

    // 从每个块中取出最小的元素并排序
    vector<int> minValues(numBlocks);
    vector<bool> isBlockEmpty(numBlocks);
    for (int i = 0; i < numBlocks; i++) {
        if (!tempFiles[i]->eof()) {
            tempFiles[i]->read((char*)&minValues[i], sizeof(int));
        } else {
            isBlockEmpty[i] = true;
        }
    }

    while (true) {
        // 找到最小的元素
        int minIndex = -1;
        int minValue = INT_MAX;
        for (int i = 0; i < numBlocks; i++) {
            if (!isBlockEmpty[i] && minValues[i] < minValue) {
                minIndex = i;
                minValue = minValues[i];
            }
        }

        if (minIndex == -1) {
            break; // 所有块都已经读取完毕
        }

        // 将最小的元素写入输出文件
        out.write((char*)&minValue, sizeof(int));

        // 从相应的块中读取下一个元素
        if (!tempFiles[minIndex]->eof()) {
            tempFiles[minIndex]->read((char*)&minValues[minIndex], sizeof(int));
        } else {
            isBlockEmpty[minIndex] = true;
        }
    }

    // 关闭所有文件并删除临时文件
    out.close();
    for (int i = 0; i < numBlocks; i++) {
        tempFiles[i]->close();
        string tempFilename = "temp_" + to_string(i) + ".dat";
        remove(tempFilename.c_str());
    }
}

int main() {
    string inputFile = "input.dat";
    string outputFile = "output.dat";
    int blockSize = 1024; // 每个块可以容纳的字节数

    externalSort(inputFile, outputFile, blockSize);

    return 0;
}