置换——选择排序

置换-选择排序（外部排序）

置换-选择排序（Replacement Selection Sort） 是外部排序的一种优化方法，广泛应用于大规模数据排序中。当我们面对不能全部装入内存的数据时，外部排序可以帮助我们有效地处理这些数据。置换-选择排序主要用于 归并排序 的阶段，它能够减少归并时的磁盘读写次数。

置换-选择排序的实现原理

置换-选择排序的基本思路是利用 堆 数据结构来维护一个“排序的候选区”，并通过合并已有的有序块来有效地处理大量外部数据。具体流程如下：

1. 初始化堆：将输入数据分成若干个块，每块数据在内存中排序，并且使用最小堆（或最大堆）来帮助归并。
2. 逐步选择：每次从堆中取出最小（或最大）元素，将其输出到输出文件中，并且将新的元素插入堆中。
3. 完成归并：重复上述步骤直到所有数据都被排序并输出。

主要步骤

1. 分块：首先，将数据文件分成多个块，每个块可以在内存中处理。
2. 维护堆：每次从堆中取出最小元素，将其输出到最终文件中，并把当前块的新元素插入堆中。
3. 循环迭代：重复这一过程直到所有块的元素都被排完。

代码实现

下面的 C++ 代码实现了 置换-选择排序 的外部排序。

cpp

#include <iostream>
#include <fstream>
#include <vector>
#include <climits>

using namespace std;

struct MinHeapNode {
    int value;
    int fileIndex;  // 记录数据来源的块
    int indexInFile; // 记录该块中的位置

    bool operator>(const MinHeapNode& other) const {
        return value > other.value;
    }
};

// 堆化函数（确保最小堆性质）
void heapify(vector<MinHeapNode>& heap, int n, int root) {
    int smallest = root;
    int left = 2 * root + 1;
    int right = 2 * root + 2;

    if (left < n && heap[left].value < heap[smallest].value)
        smallest = left;
    if (right < n && heap[right].value < heap[smallest].value)
        smallest = right;

    if (smallest != root) {
        swap(heap[root], heap[smallest]);
        heapify(heap, n, smallest);
    }
}

// 从块文件读取一个数据
bool readNextData(ifstream& file, int& data) {
    return file >> data;
}

// 分块排序并生成外部文件
void sortChunk(const string& inputFile, const string& outputFile, int chunkSize, int startPos) {
    ifstream inFile(inputFile);
    ofstream outFile(outputFile);

    inFile.seekg(startPos * sizeof(int), ios::beg);
    vector<int> chunk(chunkSize);

    // 读取数据
    int i = 0;
    for (; i < chunkSize && inFile >> chunk[i]; ++i);

    // 排序数据块
    sort(chunk.begin(), chunk.begin() + i); // 只排序有效数据部分

    // 写回排序后的数据块
    for (int j = 0; j < i; ++j)
        outFile << chunk[j] << " ";
}

// 置换-选择排序
void replacementSelectionSort(const vector<string>& inputFiles, const string& outputFile, int chunkSize) {
    priority_queue<MinHeapNode, vector<MinHeapNode>, greater<MinHeapNode>> minHeap;
    vector<ifstream> inFiles(inputFiles.size());

    // 打开所有输入文件
    for (int i = 0; i < inputFiles.size(); ++i) {
        inFiles[i].open(inputFiles[i]);
    }

    ofstream outFile(outputFile);

    // 将每个文件的第一个元素插入堆中
    for (int i = 0; i < inputFiles.size(); ++i) {
        int value;
        if (readNextData(inFiles[i], value)) {
            minHeap.push({value, i, 1});
        }
    }

    // 归并排序
    while (!minHeap.empty()) {
        MinHeapNode root = minHeap.top();
        minHeap.pop();

        // 输出最小元素
        outFile << root.value << " ";

        // 如果该块文件还有剩余数据，读取下一个数据并插入堆
        int nextValue;
        if (readNextData(inFiles[root.fileIndex], nextValue)) {
            minHeap.push({nextValue, root.fileIndex, root.indexInFile + 1});
        }
    }

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

// 外部排序主函数
void externalSort(const string& inputFile, const string& outputFile, int chunkSize) {
    ifstream inFile(inputFile);
    vector<string> chunkFiles;
    int startPos = 0;

    // 分割大文件
    while (!inFile.eof()) {
        string chunkFile = "chunk_" + to_string(startPos) + ".txt";
        chunkFiles.push_back(chunkFile);
        sortChunk(inputFile, chunkFile, chunkSize, startPos);
        startPos += chunkSize;
    }

    // 使用置换选择排序进行归并
    replacementSelectionSort(chunkFiles, outputFile, chunkSize);
}

int main() {
    string inputFile = "large_data.txt";  // 假设输入是一个非常大的文件
    string outputFile = "sorted_data.txt";
    int chunkSize = 100; // 每次处理的数据块大小

    externalSort(inputFile, outputFile, chunkSize);

    cout << "文件排序完成！" << endl;
    return 0;
}

代码解析

1. 分块排序：sortChunk 函数负责将输入文件分割成多个小块，并对每个块进行内存排序。排序后的数据写回到磁盘中，生成多个临时文件。
2. 最小堆归并：replacementSelectionSort 函数负责使用最小堆对多个已排序的块文件进行归并。堆中维护每个文件的当前最小元素，每次从堆中取出最小元素并输出到最终文件，然后再将该文件的下一个元素插入堆中。
3. 外部排序主函数：externalSort 函数协调整个过程，首先将大文件分割成多个小块并对每个块进行排序，然后调用 replacementSelectionSort 来将所有已排序的小块合并成一个大文件。

复杂度分析

1. 分块排序：每个块的排序时间为 O(M log M)，其中 M 为每个块的大小。
2. 堆归并：归并阶段的时间复杂度为 O(N log K)，其中 N 为总数据量，K 为分块文件的数量。最小堆的维护和操作需要 O(log K) 的时间。

总结

置换-选择排序是一种优化的外部排序方法，利用最小堆来维护排序的候选区，能够高效地处理大规模数据。通过合理地分割数据并使用最小堆归并，能够减少磁盘读写次数，提高排序效率。