本文主要是介绍深入理解归并排序,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
目录
一、概念
二、递归版实现
三、非递归实现
三、文件归并排序
小结
一、概念
归并排序(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;}}
}
小结
本文对于归并排序做了较为深入的讲述。主要讲述了:归并排序的递归版、非递归版以及文件归并排序问题。大家重点掌握归并排序即可,对于学有余力者,可研究其文件归并排序。好了,本文的内容到这里就结束了,如果觉得有帮助,还请一键三连多多支持一下吧!
完!
这篇关于深入理解归并排序的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!