计算机

发布日期: 2025-03-23

更新日期: 2025-03-23

文章字数: 3.6k

阅读时长: 15 分

阅读次数:

多路归并排序（K-Way Merge Sort）

1. 多路归并排序的基本原理

多路归并排序（K-Way Merge Sort）是归并排序的一种扩展，它可以将待排序数组划分成K 份，并使用K 路归并的方法进行排序。相比于二路归并排序（Merge Sort），多路归并排序适用于更大规模数据排序，常见于外部排序（如大文件排序）。

多路归并的步骤

划分数组：
- 将原始数组分成 K 份。
对子数组进行排序：
- 使用递归或其他排序算法分别对每个子数组进行排序（如果数据量较大，可继续递归执行多路归并）。
合并 K 个有序序列：
- 采用K 路归并，将 K 份已排序的子数组合并为一个完整的有序数组。

2. 代码实现

(1) K 路归并排序实现

#include <iostream>

using namespace std;

const int K = 3;  // K 路归并（可调整）

// **合并 K 路有序数组**
void kWayMerge(int arr[], int left, int mid[], int right, int k) {
    int* temp = new int[right - left + 1]; // 临时数组
    int* indices = new int[k]; // 记录 K 个数组的起始索引
    int segmentSize = (right - left + 1) / k; // 每个子数组的大小
    int minIndex, minValue;

    // 初始化 K 个起始索引
    for (int i = 0; i < k; i++) {
        indices[i] = (i == 0) ? left : mid[i - 1] + 1;
    }

    int tempIndex = 0;

    // K 路归并
    while (true) {
        minIndex = -1;
        minValue = 1e9; // 设定一个足够大的初始值

        // 在 K 路中寻找最小值
        for (int i = 0; i < k; i++) {
            if (indices[i] <= (i == k - 1 ? right : mid[i])) {
                if (arr[indices[i]] < minValue) {
                    minValue = arr[indices[i]];
                    minIndex = i;
                }
            }
        }

        // 如果所有段都处理完了，则终止
        if (minIndex == -1) break;

        // 取出最小值放入 temp，并移动指针
        temp[tempIndex++] = arr[indices[minIndex]];
        indices[minIndex]++;
    }

    // 复制回原数组
    for (int i = 0; i < tempIndex; i++) {
        arr[left + i] = temp[i];
    }

    delete[] temp;
    delete[] indices;
}

// **K 路归并排序**
void kWayMergeSort(int arr[], int left, int right, int k) {
    if (left >= right) return;  // 递归终止条件，确保不会无限递归

    int segmentSize = (right - left + 1) / k; // 每个子数组的大小
    if (segmentSize == 0) {
        // 若 segmentSize 过小，则改用普通归并排序
        k = 2;
        segmentSize = (right - left + 1) / k;
    }

    int* mid = new int[k - 1];

    // 计算 K 个分界点
    for (int i = 0; i < k - 1; i++) {
        mid[i] = left + (i + 1) * segmentSize - 1;
        if (mid[i] >= right) {
            mid[i] = right - 1;
        }
    }

    // 递归排序 K 段
    int start = left;
    for (int i = 0; i < k; i++) {
        int end = (i == k - 1) ? right : mid[i];
        kWayMergeSort(arr, start, end, k);
        start = end + 1;
    }

    // 合并 K 段
    kWayMerge(arr, left, mid, right, k);

    delete[] mid;
}

// **测试代码**
int main() {
    int arr[] = { 10, 3, 7, 8, 15, 2, 9, 1, 5, 12, 14, 6, 4, 11, 13 };
    int size = sizeof(arr) / sizeof(arr[0]);

    cout << "排序前：";
    for (int i = 0; i < size; i++) cout << arr[i] << " ";
    cout << endl;

    kWayMergeSort(arr, 0, size - 1, K);  // 执行 K 路归并排序

    cout << "排序后：";
    for (int i = 0; i < size; i++) cout << arr[i] << " ";
    cout << endl;

    return 0;
}

3. 代码解析

(1) `kWayMergeSort()` - 递归多路归并排序

先将数组划分为 K 份，确定K 个子数组的范围。
递归调用 kWayMergeSort() 对每个子数组进行排序。
最后调用 kWayMerge() 执行 K 路归并，合并 K 个有序子数组。

(2) `kWayMerge()` - K 路归并

维护 K 个子数组的起始索引，每次选出当前最小值放入临时数组 temp[]，并移动对应子数组的索引。
直到所有子数组都归并完毕，将 temp[] 复制回原数组 arr[]。

4. 时间复杂度分析

(1) 递归部分

每次划分成 K 个子数组，递归调用 kWayMergeSort()，递归深度 logₖ(n)。

(2) 归并部分

归并 K 路子数组的时间复杂度为 O(n)（因为每个元素被访问一次）。

(3) 总时间复杂度

T(n) = K*T(n/K) + O(n)
采用主定理（Master Theorem）

计算：
- 当 K = 2 时（即普通归并排序），时间复杂度：O(n log n)
- 当 K > 2 时，时间复杂度仍为 O(n log n)，但常数因子更小，因此多路归并比二路归并排序更快。

5. 特点与应用

✅ 适用于超大规模数据排序（外部排序）
✅ 相比二路归并，减少了归并次数，提高效率
✅ 时间复杂度 O(n log n)，比普通归并排序常数项更优
✅ 适合外部排序（如磁盘数据排序），可减少 I/O 操作
❌ 占用额外空间 O(n)（需要一个临时数组）
❌ 适用于大数据但不适用于小规模数据（小规模数据快排更优）

6. 总结

多路归并排序是一种归并排序的改进版本，通过将数据划分为 K 份，并使用 K 路归并提高效率。
相比普通归并排序，K 路归并减少了归并次数，适合超大规模数据排序（如磁盘排序、外部排序）。
纯原生 C++ 实现，不使用 STL，严格按照 K 路归并的原理手写。

最小堆优化 K 路归并

在之前的 K 路归并排序 中，我们使用了线性扫描的方法找到当前最小的元素，每次都要遍历 K 个数组来寻找最小值，这导致了 O(K) 的查找复杂度，整体排序复杂度为 O(n log n) 但 log K 较大。

我们可以使用最小堆（小根堆）优化 K 路归并，它的关键点在于：

使用最小堆存储 K 个子数组的当前最小元素索引。
堆顶元素始终是当前最小的元素，弹出后立即补充该元素的下一个元素，保持堆的大小为 K。
查找最小值的复杂度由 O(K) 降低为 O(log K)，从而提升归并效率。

📌 代码实现

#include <iostream>

using namespace std;

// 定义最小堆节点结构
struct MinHeapNode {
    int value;  // 存储当前值
    int index;  // 该值所在的原数组索引
    int nextPos; // 该值在对应数组中的下一个位置索引
};

// **小根堆调整函数（堆化）**
void heapify(MinHeapNode heap[], int size, int root) {
    int smallest = root;  
    int left = 2 * root + 1;  
    int right = 2 * root + 2;

    if (left < size && heap[left].value < heap[smallest].value)
        smallest = left;
    if (right < size && heap[right].value < heap[smallest].value)
        smallest = right;
    
    if (smallest != root) {
        swap(heap[root], heap[smallest]);
        heapify(heap, size, smallest);
    }
}

// **K 路归并排序（基于最小堆）**
void kWayMergeSort(int arr[], int left, int right, int k) {
    if (left >= right) return; // 递归终止

    int size = right - left + 1;
    int segmentSize = size / k;
    if (segmentSize == 0) { k = 2; segmentSize = size / k; } // 限制 K 值，防止分块过小

    int *mid = new int[k - 1]; 

    // 计算 K 个子数组的分界点
    for (int i = 0; i < k - 1; i++) {
        mid[i] = left + (i + 1) * segmentSize - 1;
        if (mid[i] >= right) mid[i] = right - 1;
    }

    // 递归排序 K 个子数组
    int start = left;
    for (int i = 0; i < k; i++) {
        int end = (i == k - 1) ? right : mid[i];
        kWayMergeSort(arr, start, end, k);
        start = end + 1;
    }

    // **使用最小堆进行 K 路归并**
    MinHeapNode *heap = new MinHeapNode[k];
    int *indices = new int[k]; // 记录 K 个子数组的起始索引

    // 初始化最小堆
    for (int i = 0; i < k; i++) {
        indices[i] = (i == 0) ? left : mid[i - 1] + 1;
        heap[i] = { arr[indices[i]], i, indices[i] + 1 };
    }

    // 构建初始最小堆
    for (int i = k / 2 - 1; i >= 0; i--)
        heapify(heap, k, i);

    // 归并排序
    int tempIndex = 0;
    int *temp = new int[size];

    while (true) {
        // 取出堆顶元素（最小值）
        MinHeapNode root = heap[0];
        temp[tempIndex++] = root.value;

        // 移动索引
        if (root.nextPos <= (root.index == k - 1 ? right : mid[root.index])) {
            heap[0] = { arr[root.nextPos], root.index, root.nextPos + 1 };
        } else {
            // 若当前数组已经用完，则用 INT_MAX 代替
            heap[0] = { INT_MAX, -1, -1 };
        }

        // 重新堆化
        heapify(heap, k, 0);

        // 结束条件：所有数据归并完
        if (heap[0].value == INT_MAX) break;
    }

    // 复制回原数组
    for (int i = 0; i < size; i++) {
        arr[left + i] = temp[i];
    }

    // 释放内存
    delete[] heap;
    delete[] indices;
    delete[] temp;
    delete[] mid;
}

// **测试代码**
int main() {
    int arr[] = {10, 3, 7, 8, 15, 2, 9, 1, 5, 12, 14, 6, 4, 11, 13};
    int size = sizeof(arr) / sizeof(arr[0]);

    cout << "排序前：";
    for (int i = 0; i < size; i++) cout << arr[i] << " ";
    cout << endl;

    kWayMergeSort(arr, 0, size - 1, 3); // K = 3 进行 K 路归并排序

    cout << "排序后：";
    for (int i = 0; i < size; i++) cout << arr[i] << " ";
    cout << endl;

    return 0;
}

📌 代码优化点

1. 用最小堆替代线性搜索

✅ 传统 K 路归并需要 O(K) 查找最小值，优化后使用小根堆只需 O(log K)。

2. 堆化逻辑

✅ heapify 维护小根堆，使堆顶始终是当前最小元素。

3. 归并时动态维护最小值

✅ 堆顶元素弹出后，立即补充相应子数组的下一个元素。

4. 终止条件

✅ 所有 K 个子数组遍历完成后，堆顶设为 INT_MAX 作为哨兵，防止溢出。

📌 复杂度分析

操作	时间复杂度
初始建堆	O(K)
每次插入最小值并调整堆	O(log K)
总归并次数（N 次插入）	O(N log K)

✅ 总时间复杂度： O(N log K)，比 O(NK) 线性搜索方案 更快。

📌 适用场景

✅ 适用于 K 个有序数组归并
✅ 适用于 海量数据排序（外部排序）
✅ 适用于 高效合并多个有序文件（如搜索引擎索引构建）

📌 总结

最小堆优化 K 路归并，将查找最小值复杂度从 O(K) 降低到 O(log K)。
避免了递归深度过深的问题，确保 K 过大时仍然高效。
比传统的 K 路归并更适合大规模数据排序。

优化 I/O 适用于外部排序（磁盘数据排序）和迭代版本的实现可以让我们更高效地处理海量数据，尤其是在内存不足以加载全部数据的情况下。外部排序通过将数据分成较小的块，每块单独排序后再进行归并，避免了内存溢出的问题。迭代版本则避免了递归带来的栈溢出问题，并且能够处理更大的数据集。

外部排序优化

外部排序的主要思路：

分块读取：首先将大文件分割成多个小文件，每个文件都在内存中进行排序。
归并过程：通过多路归并将这些排序后的小文件合并为一个大文件。可以使用最小堆来优化归并操作。

迭代版本优化

递归版本可能会因为深度过大而导致栈溢出。为了避免这种情况，我们可以将递归转换成迭代，使用堆结构进行合并。

外部排序：使用最小堆优化 I/O

外部排序的核心是 K 路归并，我们将磁盘上的多个块文件逐一读入内存并进行合并。

外部排序流程：

分割文件：将大文件拆分成多个小文件，每个小文件可以在内存中排序并写回磁盘。
K 路归并：使用最小堆来合并这些排序好的小文件。

代码实现：

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

using namespace std;

// 定义最小堆节点
struct MinHeapNode {
    int value;
    int fileIndex;
    int indexInFile;

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

// 分块排序函数
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);
    
    // 读取数据
    for (int i = 0; i < chunkSize && inFile >> chunk[i]; ++i);

    // 排序数据块
    sort(chunk.begin(), chunk.end());

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

// 合并所有分块文件
void externalMerge(const vector<string>& chunkFiles, const string& outputFile) {
    priority_queue<MinHeapNode, vector<MinHeapNode>, greater<MinHeapNode>> minHeap;
    vector<ifstream> inFiles(chunkFiles.size());

    // 打开所有分块文件
    for (int i = 0; i < chunkFiles.size(); ++i)
        inFiles[i].open(chunkFiles[i]);

    // 将每个分块文件的第一个元素放入堆中
    for (int i = 0; i < chunkFiles.size(); ++i) {
        int value;
        if (inFiles[i] >> value)
            minHeap.push({value, i, 1});  // 文件索引, 当前值, 当前索引
    }

    ofstream outFile(outputFile);
    while (!minHeap.empty()) {
        MinHeapNode root = minHeap.top();
        minHeap.pop();

        // 写入最小值
        outFile << root.value << " ";

        // 读取并插入下一个元素
        int value;
        if (inFiles[root.fileIndex] >> value) {
            minHeap.push({value, 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;
    }

    // 使用最小堆归并所有文件
    externalMerge(chunkFiles, outputFile);
}

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

    externalSort(inputFile, outputFile, chunkSize);

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

代码说明：

分块排序：sortChunk 函数负责将大文件分割成小块，并在内存中对每个小块进行排序，之后写回磁盘。
最小堆归并：externalMerge 函数使用最小堆来归并多个已排序的分块文件。每个文件的第一个元素首先被插入堆中，然后将堆顶元素弹出并读取该文件的下一个元素，直到所有文件归并完。
外部排序：externalSort 函数负责协调整个过程，包括文件分割、排序和归并。

复杂度分析：

每个分块的排序时间：O(M log M)，其中 M 是每个块的大小。
归并的时间：O(N log K)，其中 N 是总数据量，K 是分块的数量。

迭代版本的优化

递归版本可能会因栈深度过大导致栈溢出。为了避免递归，我们可以改为迭代版本，利用一个栈或者队列来模拟递归的栈调用。

迭代版本的实现：

#include <iostream>
#include <stack>
#include <vector>

using namespace std;

// 堆化函数（保持最小堆性质）
void heapify(MinHeapNode heap[], int size, int root) {
    int smallest = root;
    int left = 2 * root + 1;
    int right = 2 * root + 2;

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

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

// 迭代版 K 路归并排序
void iterativeKWayMergeSort(int arr[], int left, int right, int k) {
    stack<pair<int, int>> mergeStack;
    mergeStack.push({left, right});

    while (!mergeStack.empty()) {
        pair<int, int> range = mergeStack.top();
        mergeStack.pop();
        int start = range.first, end = range.second;
        if (start < end) {
            int mid = (start + end) / 2;
            mergeStack.push({start, mid});
            mergeStack.push({mid + 1, end});
            kWayMergeSort(arr, start, mid, k);
            kWayMergeSort(arr, mid + 1, end, k);
        }
    }
}

总结：

外部排序适用于磁盘数据排序，使用最小堆进行归并。
迭代版本的优化避免了栈溢出的风险，通过显式堆栈来模拟递归。

这两种优化可以有效处理大规模数据，避免内存限制和栈溢出问题。

Gustavo

https://gustavo1841.github.io/2025/03/23/ji-suan-ji/shu-ju-jie-gou/suan-fa/pai-xu/gui-bing-pai-xu-wai-pai-xu-fang-shi/

本博客所有文章除特別声明外，均采用 CC BY-NC 4.0 许可协议。转载请注明来源 Gustavo !

计算机数据结构算法

置换——选择排序

2025-03-23 计算机

计算机数据结构算法

堆排序

2025-03-23 计算机

计算机数据结构算法

归并排序——外排序方式

多路归并排序（K-Way Merge Sort）

1. 多路归并排序的基本原理

多路归并的步骤

2. 代码实现

(1) K 路归并排序实现

3. 代码解析

(1) kWayMergeSort() - 递归多路归并排序

(2) kWayMerge() - K 路归并

4. 时间复杂度分析

(1) 递归部分

(2) 归并部分

(3) 总时间复杂度

5. 特点与应用

6. 总结

最小堆优化 K 路归并

📌 代码实现

📌 代码优化点

1. 用最小堆替代线性搜索

2. 堆化逻辑

3. 归并时动态维护最小值

4. 终止条件

📌 复杂度分析

📌 适用场景

📌 总结

外部排序优化

迭代版本优化

外部排序：使用最小堆优化 I/O

外部排序流程：

代码实现：

代码说明：

复杂度分析：

迭代版本的优化

迭代版本的实现：

总结：

(1) `kWayMergeSort()` - 递归多路归并排序

(2) `kWayMerge()` - K 路归并