Skip to content

Latest commit

 

History

History
156 lines (111 loc) · 3.9 KB

8.merge_sort.md

File metadata and controls

156 lines (111 loc) · 3.9 KB
Raw

MERGE SORT

最重要的过程是回溯，也就是两个数组合并成一个有序数组的过程。这个过程才实现了排序，并且需要额外的存储空间

这就是分治（Divide and Conquer）

void merge_sort(int *arr, int l, int r) {
    // 递归的边界条件：只有一个元素就不用排序
    if (l >= r) return ;
    int mid = (l + r) >> 1;
    merge_sort(arr, l, mid);
    merge_sort(arr, mid + 1, r);
    // 因为是回溯过程才实现的排序
    // 所以写在递归下面
    // 递归深度logn 空间开销是logn ^ 2
    int *temp = (int *)malloc(sizeof(int) * (r - l + 1));
    int k = 0, p1 = l, p2 = mid + 1;
    while (p1 <= mid || p2 < r) {
        // 两种情况将拿左边
        // 1. 右边没元素了
        // 2. 左边元素有并且较小
        if ((p2 > r) || (p1 <= mid && arr[p1] <= arr[p2])) {
            temp[k++] = arr[p1++];
        } else {
            temp[k++] = arr[p2++];
        }
    }
    for (int i = l; i <= r; i++) arr[i] = temp[i - l];
    free(temp);
    return ;
}

从二路归并到多路归并

变路归并：每一层的归并路数可能都不一样

归并排序在大数据中很多应用

在合的时候会用到额外的存储空间temp数组，

注意此存储空间只需要支持向尾部追加数据就可以。

不一定是内存中的数组，

在硬盘里的文件也可以作为此数组空间（文件IO）

所以对与一个经典的题:

电脑内存大小2GB，如何对一个40GB的文件进行排序？

为什么不能用快排？

快排需要我们对整个数组进行排序，也就是整个数组要读进内存

就用20路归并排序每次对2GB排序，之后在硬盘（temp数组）进行整合的过程，

这也是归并排序为什么叫做外部排序-可以用外部的存储空间。

在每次对20个数据进行合的时候用小顶堆。

算法思想：分治----先处理左边，后处理右边。得到两边的信息后处理横跨左右两边的信息

模拟对大文件排序
int main(int argc, char *argv[]) {
    int n = argc - 1;
    FILE **farr = (FILE **)malloc(sizeof(FILE *) * n);
    for (int i = 1; i < n + 1; i++) farr[i - 1] = fopen(argv[i], "r");
    for (int i = 0; i < n; i++) {
        int a;
        // 这种方式只存储了两个文件指针
        // 并没有将文件全部的内容一次性的读入内存
        // 而是需要一个就取一个
        while (fscanf(farr[i], "%d", &a) != EOF) {
            printf("%d\n", a);
        }
        printf("---------EOF----------\n");
    }
    return 0;
}
实现对文件排序
struct Data {
    FILE *fin;
    int val, flag;
};

int main(int argc, char *argv[]) {
    int n = argc - 1;
    Data *data = (Data *)malloc(sizeof(Data) * n);
    for (int i = 1; i < n + 1; i++) {
        data[i - 1].fin = fopen(argv[i], "r");
        if (fscanf(data[i - 1].fin, "%d", &data[i - 1].val) == EOF) {
            // 将文件指针存进来 flag = 1表示此指针指向了文件
            data[i - 1].flag = 1;
        } else {
            data[i - 1].flag = 0;
        }
    }
    FILE *fout = fopen("output", "w");
    while (true) {
        int flag = 0;
        int ind = -1;
        for (int i = 0; i < n; i++) {
            if (data[i].flag) continue;
            if (ind == -1 || data[i].val < data[ind].val) {
                // 找到最小的
                ind = i;
            }
        }
        if (ind != -1) {
            fprintf(fout, "%d\n", data[ind].val);
            if (fscanf(data[ind].fin, "%d", &data[ind].val) == EOF) {
                data[ind].flag = 1;
            } else {
                data[ind].flag = 0;
            }
            flag = 1;
        }
        if (flag == 0) break;
    }
    return 0;
}

核心思想：

处理左边，得到左边的信息

处理右边，得到右边的信息

处理横跨左右两边的信息