深入理解归并排序
目录
一、概念
二、递归版实现
三、非递归实现
三、文件归并排序
小结
一、概念
归并排序（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;
}
}
}小结
本文对于归并排序做了较为深入的讲述。主要讲述了：归并排序的递归版、非递归版以及文件归并排序问题。大家重点掌握归并排序即可，对于学有余力者，可研究其文件归并排序。好了，本文的内容到这里就结束了，如果觉得有帮助，还请一键三连多多支持一下吧！
完！