分治法之合并排序(2021/1/23)-白红宇

分治法之合并排序(2021/1/23)

阅读量：685 次

发布时间：2019-03-17

本文共 1608 字，大约阅读时间需要 5 分钟。

之后的代码版本：

问题引入部分：用户需要一个能够对多个 integers 进行排序的程序。这个问题可以通过递归方法实现，具体来说，可以采用归并排序的思路来解决。

代码实现部分：

#include 
   
    
#include 
    
     
using namespace std;
struct Data {
    int flag;
};
void MergeFunction(struct Data* list, int low, int middle, int high) {
    int size = high - low;
    struct Data* space = (struct Data*) malloc(sizeof(struct Data) * size);
    int i = low;
    int j = middle + 1;
    int now = 0;
    while (i <= middle && j <= high) {
        if (list[i].flag <= list[j].flag) {
            space[now++] = list[j++];
        } else {
            space[now++] = list[i++];
        }
    }
    // 处理剩余部分
    while (i <= middle) {
        space[now++] = list[i++];
    }
    while (j <= high) {
        space[now++] = list[j++];
    }
    // 将space的内容放回到原来的数组中
    for (int k = low; k <= high; ++k) {
        list[k] = space[k - low];
        free(space);
    }
}
void mergesort(struct Data* list, int low, int high) {
    if (low >= high) {
        // 只有一个元素，不需要排序
        return;
    }
    int middle = (low + high) / 2;
    // 分别对左右子数组进行排序
    mergesort(list, low, middle);
    mergesort(list, middle + 1, high);
    // 合并有序的两个子数组
    MergeFunction(list, low, middle, high);
}
int main() {
    struct Data list[5] = { {34}, {5}, {2}, {7}, {10} };
    // 开始排序
    mergesort(list, 0, 4);
    // 输出结果
    for (int i = 0; i < 5; ++i) {
        cout << " " << list[i].flag;
    }
    return 0;
}