深入理解归并排序

一、概念

二、递归版实现

三、非递归实现

三、文件归并排序

小结

一、概念

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

其思想可用下图来表示：

从上图我们可以看到，归并的大体思路为：先保证小区间有序，再保证大区间有序。在思想上体现出了：分而治之的理念。

可总结为以下两点：

将待排序的线性表不断地切分成若干个子表，直到每个子表只包含一个元素，这时，可以认为只包含一个元素的子表是有序表。
将子表两两合并，每合并一次，就会产生一个新的且更长的有序表，重复这一步骤，直到最后只剩下一个子表，这个子表就是排好序的线性表。

二、递归版实现

对于用递归实现这个排序，我们可这样解决：

1. 开辟一个新数组，用于存放每次排完序的值。

2. 找到这个数组的最小单位，两两比较。

3. 每完成一组排序，便把新数组拷贝给原数组。

4. 重复以上操作，直到排序完成。

代码实现：

void _MergeSort(int* a, int* tmp, int left, int right)
{if (left >= right){return;}int mid = (left + right) / 2;// 如果[begin, mid][mid+1, end]有序就可以进行归并了_MergeSort(a, tmp, left, mid);_MergeSort(a, tmp, mid + 1, right);//归并int begin1 = left, end1 = mid;int begin2 = mid + 1, end2 = right;int i = left;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] <= a[begin2]){tmp[i++] = a[begin1++];}else{tmp[i++] = a[begin2++];}}while (begin1 <= end1){tmp[i++] = a[begin1++];}while (begin2 <= end2){tmp[i++] = a[begin2++];}memcpy(a + left, tmp + left, sizeof(int) * (right - left + 1));
}void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}_MergeSort(a, tmp, 0, n - 1);free(tmp);tmp = NULL;
}

三、非递归实现

我们用递归解决这个排序似乎是件较容易的事情，但对于我们想要用非递归实现来说，仍有不小的挑战。我们说一下实现思路：

1.我们要解决如何实现分组问题

2.我们引入gap变量用它来进行控制分组

3.分组运用gap不同的值来确定每个组的大小，从小往大依次来实现归并。

注意点：

1. 当第二组开始位置 超过 / 等于 该数组长度时，我们此时可认为以排序完成，break即可。

2. 当第二组结束位置 超过 / 等于 该数组长度时，我们要将其大小置为n-1。

代码实现如下：

void MergeSortNonR(int* a, int n)
{int* tmp = malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}int gap = 1;while (gap < n){for (int i = 0; i < n; i += 2 * gap){// [begin1, end1][begin2, end2]int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;// 第二组都越界不存在，这一组就不需要归并if (begin2 >= n){break;}// 第二的组begin2没越界，end2越界了，需要修正一下，继续归并if (end2 >= n){end2 = n - 1;}int j = i;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[j++] = a[begin1++];}else{tmp[j++] = a[begin2++];}}while (begin1 <= end1){tmp[j++] = a[begin1++];}while (begin2 <= end2){tmp[j++] = a[begin2++];}}gap *= 2;}memcpy(a + n - 1, tmp + n - 1, sizeof(int) * (n - 1));free(tmp);tmp = NULL;
}

这里大家估计会有点小疑惑，疑惑什么呢？为什么不能tmp归并完我们在把它拷给a，一步一步拷不麻烦吗？

我们能不能直接拷呢？大家可以去操作一下，答案很显然：不可以！原因如下：

这个本身的话，就是每次循环结束，在拷贝数组和临时数组的值进行交换，之后就是在临时数组改变之后的情况下，在进行第二次循环排序，之后。把拷贝后的数据在进行分组合并，每次循环里面都是对a合并后的数据在做处理，如果说全部执行完再拷贝，那a每次并没有啥变化，当然就不可能完成归并排序整个过程。

各位感兴趣的话可以打印验证一下。

三、文件归并排序

关于这个问题，我们给出以下情景：在今年，你怀着忐忑的心情去参加秋招，顺利通过了笔试，在面试时，面试官的问题你都对答入流，直到最后一题：给你1G的空间，你如何使10G的数据有序，这时，你看过本博主写得TOP-K问题（二叉树——堆详解_堆二叉树-CSDN博客），你自信满满的回答了这个问腿，面试官觉得你很不错，便提问到：如果用归并该如何解决呢？你不由想起了这篇博客，也就是目前各位读者所看的这篇，以下是解题思路：

1. 首先，先创建三个文件：file1，file2，mfine。

2.读取n个值排序后写到file1，再读取n个值排序后写到file2

        3. file1和file2利⽤归并排序的思想，依次读取⽐较，取⼩的尾插到mfile，mfile归并为⼀个有序⽂件

        4. 将file1和file2删掉，mfile重命名为file1

        5. 再次读取n个数据排序后写到file2

        6. 继续⾛file1和file2归并，重复步骤2，直到⽂件中⽆法读出数据。最后归并出的有序数据放到了 file1中

对于删掉文件和改文件名，我们可通过remove 和rename 函数来完成（可点击查看其用法）。

代码实现：

//造数据
void CreateNDate()
{const char* file = "text.txt";FILE* fin = fopen(file, "w");if (fin == NULL){perror("fail error");return;}srand((unsigned)time(NULL));int n = 100;for (int i = 0; i < n; i++){int x = rand() + i;fprintf(fin, "%d\n", x);}fclose(fin);
}
int comper(const void* p1, const void* p2)
{return (*(int*)p1 - *(int*)p2);
}// 返回实际读到的数据个数，没有数据了，返回0
int ReadNDataSortToFile(FILE* fout, int n, const char* file)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){return 0;}int x = 0;// 想读取n个数据，如果遇到文件结束，应该读到j个int j = 0;for (int i = 0; i < n; i++){if (fscanf(fout, "%d", &x) == EOF){break;}tmp[j++] = x;}if (j == 0){free(tmp);return 0;}//快排qsort(tmp, j, sizeof(int), comper);FILE* fin = fopen(file, "w");if (fin == NULL){perror("file error");return 0;}// 写回file1文件for (int i = 0; i < j; i++){fprintf(fin, "%d\n", tmp[i]);}free(tmp);fclose(fin);return j;
}void MergeFile(const char* file1, const char* file2, const char* mfile)
{FILE* fin1 = fopen(file1, "r");if (fin1 == NULL){perror("file error");return;}FILE* fin2 = fopen(file2, "r");if (fin2 == NULL){perror("file error");return;}FILE* mfin = fopen(mfile, "w");if (mfin == NULL){perror("file fail");return;}//归并逻辑int x1 = 0, x2 = 0;int ret1 = fscanf(fin1, "%d", &x1);int ret2 = fscanf(fin2, "%d", &x2);while (ret1 != EOF && ret2 != EOF){if (x1 < x2){fprintf(mfin, "%d\n", x1);ret1 = fscanf(fin1, "%d", &x1);}else{fprintf(mfin, "%d\n", x2);ret2 = fscanf(fin2, "%d", &x2);}}while (ret1 != EOF){fprintf(mfin, "%d\n", x1);ret1 = fscanf(fin1, "%d", &x1);}while (ret2 != EOF){fprintf(mfin, "%d\n", x2);ret2 = fscanf(fin2, "%d", &x2);}fclose(fin1);fclose(fin2);fclose(mfin);
}
void test()
{/*CreateNDate();*/const char* file1 = "file1.txt";const char* file2 = "file2.txt";const char* mfile = "mfile.txt";FILE* fout = fopen("text.txt", "r");if (fout == NULL){perror("file error");return;}int m = 10;ReadNDataSortToFile(fout, m, file1);ReadNDataSortToFile(fout, m, file2);while (1){MergeFile(file1, file2, mfile);remove(file1);remove(file2);rename(mfile, file1);if (ReadNDataSortToFile(fout, m, file2) == 0){break;}}
}