数据结构与算法 - 归并排序 #递归版本 #非递归版本 #文件归并
文章目录
前言
一、递归版本
二、非递归版本
三、文件归并
总结
前言
路漫漫其修远兮，吾将上下而求索；
一、递归版本
1、思想：
归并排序(MERGE-SORT) 是建立在归并操作上的一种有效的排序算法，该算法是采用分治法(Divide and Conquer) (分治可以理解为递归) 的一个非常典型的应用。将有序的子序列进行合并得到完全有序的序列；即先使每个子序列有序，再使得子序列段间有序。
若将两个有序的子序列合并为一个有序的序列，称为二路归并；
图解如下：
将待排序的序列分为单个数据，而单个数据的序列可以看作是一个有序的序列，合并两个有序的序列……滚雪球式的便可以完成排序，再此过程中需要额外创建一个数组来存放排好的数据；
归并排序递归版本递归的感觉与二叉树的后序遍历相似；因为所要合并的序列中的数据必须是有序的，也只有这样递归，将只有一个数据的序列看作是一个有序的序列；
参考代码：
//归并排序主逻辑
void _MergeSort(int* a, int left, int right, int* tmp)
{
//范围合法+ 数据大于等于2
if (left >= right)
return;
//有点像二叉树的后序遍历
//根据中间下标来划分
int mid = (right - left) / 2 + left;
//left, mid mid+1 ,right
_MergeSort(a, left, mid, tmp);
_MergeSort(a, mid + 1, right, tmp);
//归并排序逻辑
int begin1 = left, end1 = mid;
int begin2 = mid + 1,end2 = right;
int index = left;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tmp[index++] = a[begin1++];
}
else
{
tmp[index++] = a[begin2++];
}
}
//两序列的长度不一定相同
while (begin1 <= end1)
{
tmp[index++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[index++] = a[begin2++];
}
//将tmp 中的数据拷贝放回原数组中
memcpy(a + left, tmp + left, (right - left + 1)*sizeof(int));
}
//递归版本的归并排序
void MergeSort(int* a, int n)
{
//创建数组保存排好序的数据
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc fail");
exit(-1);
}
_MergeSort(a, 0, n - 1, tmp);
//释放动态开辟的空间
free(tmp);
tmp = NULL;
}二、非递归版本
可以通过控制gap 来控制待归并序列中的数据个数，同时可以利用gap 与下标之间的关系将序列进行划分、迭代；当gap>=n(n 为待排序列中的数据个数) 的时候，循环便结束；
代码如下：
//非递归版本的归并排序
void MergeSortNonR(int* a, int n)
{
//开辟额外的空间
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc fail");
exit(-1);
}
//gap 控制每组待排序序列中的数据个数
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;
}
//第二组的数据个数与第一组的数据个数不相同,有多少取多少
if (end2 >= n)
{
end2 = n - 1;
}
//归并逻辑
int index = i;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tmp[index++] = a[begin1++];
}
else
{
tmp[index++] = a[begin2++];
}
}
while (begin1 <= end1)
{
tmp[index++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[index++] = a[begin2++];
}
//将tmp 中的数据拷贝放回原数组中
memcpy(a + i, tmp + i, (end2 - i + 1) * sizeof(int));
}
gap *= 2;
}
//循环结束，记得释放动态开辟的空间
free(tmp);
tmp = NULL;
}
三、文件归并
在讲述文件归并之前，我们先来了解一下外排序；
外排序（External sorting）是能够处理极大数据量的排序算法；通常来说，外排序的数据不能一次性全部装入内存之中，只能放在读写较慢的外存储器之中(eg.硬盘)。外排序通常采用的是一种“排序 - 归并” 的策略。首先会将大文件中的数据分为多个部分读入内存中进行排序，当这些数据在内存中完成排序之后就会放到临时文件之中，然后依次进行，将待排序的数据组织为多个有序的临时文件。然后再归并阶段将这些临时文件组合成为一个大的有序的文件，即排序结果；
前面所述的排序都是内排序，这些排序思想适用于数据在内存当中，并且支持随机访问。而归并排序的思想无需随机访问数据，只需要依次按序列读取数据。所以归并排序即是一个内排序，又是一个外排序；
什么是“外”？
- ”外“ 指得是硬盘、磁盘；”内“通常指的是内存
什么情况之下会采用外排序？
- 当数据量极大的时候，在内存之中放不下，数据便会存放在文件当中；这个时候不能使用内排序对数据进行排序，只能使用外排序对数据进行排序；
为什么不能使用内排序对外存当中的数据进行排序？
- 因为内排序的思想是要访问数据在内存当中的一个下标的位置，磁盘当中能够支持我们去访问某个数据但是不断地变化会使得整个排序地过程性能很慢（想要访问文件中指定位置上的数据只能 遍历序列式地去读取，并且即使是序列式地访问也比在内存中挨着访问要慢很多）；
为什么归并排序可以排序外存当中的数据？
- 因为归并的思想不需要进行下标位置的随机访问；只要你有一个序列（对于归并排序来说，该序列是在内存中还是在磁盘中间均不重要）；归并的核心思想：只要这两个子序列有序便会依次读取这两个序列当中的数据进行比较，谁的值小便会写入新的空间当中；归并排序只需要线性地、挨着挨着序列式地读写；
文件归并排序思路一：
将大文件拆成一个一个的小文件，然后将小文件中的数据读到内存中进行排序，排完序之后再放入文件当中，然后再对有序地文件进行两两归并；
这种思想可行但是不好实现；例如：在不知道大文件为多大的时候，小文件究竟要多大？不知道小文件多大便就不知道要拆分为多少个小文件；
文件归并排序思路2：
注：归并要求待归并的子序列是有序的，但是并未要求两序列之中的数据个数是相等的；
- 1、读取n个值排序后写到文件 file1 之中，再读取 n 个值排序后写到文件file2 之中
- 2、file1 和fil2 利用归并的思想，依次读取比较，取小的值尾插到文件mfile 之中，mfile 是file1和file2 中数据进行归并的结果；
- 3、将file1 和file2 删掉，mfile 重命名为file1
- 4、再次读取n 个数据排序之后写到file2 中
- 5、继续将file1 和file2 中的数据归并放到mfile 之中，重复步骤2，直到文件中无法再读出数据。最后归并的结果是放在file1 之中的；
图解如下：
创建一个含有大量数据的文件，代码如下：
void CreatNDate()
{
//造数据
int n = 1000000;
//设置随机种子
srand((unsigned int)time(NULL));
//存放数据的文件名
const char* file = "data.txt";
//以写的形式打开文件
FILE* fin = fopen(file, "w");
if (fin == NULL)
{
perror("fopen fail");
exit(-1);
}
//将数据写入文件当中
for (int i = 0; i < n; i++)
{
fprintf(fin, "%d\n", i + rand());
}
//关闭文件
fclose(fin);
fin = NULL;
}通过前面的思路分析我们可以知道，文件归并排序首先是要读出前 n 个数据， n 是多少呢？如果一个一个地读数据然后归并可以吗？
- 将n 设置一个较为合适的值便可(n 个数据可以放到内存中进行排序)；可以一个一个地读数据然后归并，但是这样做地效率非常低下并且中间会产生许多小文件，而相较于在内存当中读取数据，在文件当中读取数据会慢很多，所以不建议一个一个地读数据然后进行归并；
故而我们要尽可能让一些数据在内存之中就排成有序；文件当中没有整型的概念，一个整型的数据在文件之中不一定占4byte , 它会转换成字符串进行存储的；
在file 中读取n 个数据排成有序之后再放入file1 之中；首先是需要打开文件file ，然后是从中读取n 个数据放到内存当中进行排序，排完序之后再打开文件file1 ，再将数据放到file1 之中；
频繁地打开file 文件、关闭文件还需要处理文件指针，较为麻烦，此处可以将file 文件的文件指针以参数的形式传递，这样在读文件的时候，文件指针是自动往后走的；
参考代码：
void CreatNDate()
{
//造数据
int n = 1000000;
//设置随机种子
srand((unsigned int)time(NULL));
//存放数据的文件名
const char* file = "data.txt";
//以写的形式打开文件
FILE* fin = fopen(file, "w");
if (fin == NULL)
{
perror("fopen fail");
exit(-1);
}
//将数据写入文件当中
for (int i = 0; i < n; i++)
{
fprintf(fin, "%d\n", i + rand());
}
//关闭文件
fclose(fin);
fin = NULL;
}
//qsort 的比较函数
int compare(const void* e1, const void* e2)
{
return *(int*)e1 - *(int*)e2;
}
//返回在file 中实际读到的数据的个数,没有读到数据便返回0
int ReadNDataSortToFile(FILE* fout, int n, const char* file1)
{
//将从file 中读取的数据先放在变量x中
int x = 0;
//创建数组
int* a = (int*)malloc(sizeof(int) * n);
if (a == NULL)
{
perror("malloc fail");
exit(-1);
}
//想要读取 n 个数据，变量用来记录读取到的数据的个数
int j = 0;
for (int i = 0; i < n; i++)
{
//需要判断读取是否成功
if (fscanf(fout, "%d", &x) == EOF)
break;
//将读取的数据放到数组之中
a[j++] = x;
}
//如果没有读取到数据便返回0
if (j == 0)
return 0;
//在内存中排序 - 此处使用到了qsort
qsort(a, j, sizeof(int), compare);
//打开文件file1
FILE* fin = fopen(file1, "w");
if (fin == NULL)
{
perror("ReadNDataSortToFile - fopen file1 fail");
exit(-1);
}
//将排好的数据放到文件file1 中
for (int i = 0; i < j; i++)
{
fprintf(fin, "%d\n", a[i]);
}
//释放动态开辟的空间
free(a);
a = NULL;
//关闭file1
fclose(fin);
fin = NULL;
//返回读取的数据䣌个数
return j;
}
//文件归并排序
void MergeFile(const char* file1, const char* file2, const char* mfile)
{
//打开file1
FILE* fout1 = fopen(file1, "r");
if (fout1 == NULL)
{
perror("fopen file1 fail");
exit(-1);
}
//打开file2
FILE* fout2 = fopen(file2, "r");
if (fout2 == NULL)
{
perror("fopen file2 fail");
exit(-1);
}
//打开mfile
FILE* fin = fopen(mfile, "w");
if (fin == NULL)
{
perror("fopen mfile fail");
exit(-1);
}
//将file1 与 file2 进行归并，将归并的结果放到mfile 之中
//由于file1 与 file2 之中的数据个数可能不一样，需要创建变量来接收从这两个文件中读取到的数据的返回值
//然后判断读取是否成功
int x1 = 0;
int x2 = 0;
int ret1 = fscanf(fout1, "%d", &x1);
int ret2 = fscanf(fout2, "%d", &x2);
while (ret1 != EOF && ret2 != EOF)
{
if (x1 < x2)
{
fprintf(fin, "%d\n", x1);
ret1 = fscanf(fout1, "%d", &x1);
}
else
{
fprintf(fin, "%d\n", x2);
ret2 = fscanf(fout2, "%d", &x2);
}
}
while (ret1 != EOF)
{
fprintf(fin, "%d\n", x1);
ret1 = fscanf(fout1, "%d", &x1);
}
while (ret2 != EOF)
{
fprintf(fin, "%d\n", x2);
ret2 = fscanf(fout2, "%d", &x2);
}
//关闭文件
fclose(fout1);
fclose(fout2);
fclose(fin);
}
void Test2()
{
//创建待排序的大文件
//CreatNDate();
//文件
const char* file1 = "file1.txt";
const char* file2 = "file2.txt";
const char* mfile = "mfile.txt";
//打开待排序的文件
FILE* fout = fopen("data.txt", "r");
if (fout == NULL)
{
perror("fopen file fail");
exit(-1);
}
//从fout 读取n个数据放到file1 file2 之中
int n = 10000;
ReadNDataSortToFile(fout, n, file1);
ReadNDataSortToFile(fout, n, file2);
while (1)
{
//将file1 与file2 进行归并
MergeFile(file1, file2, mfile);
//删除file1 file2
remove(file1);
remove(file2);
//将mfile 重命名为file1
int h = rename(mfile, file1);
//再读取n个数据放到file2 之中
//可能读不到数据，需要判断读取数据这个函数的返回值
int m = 0;
if ((m= ReadNDataSortToFile(fout, n, file2))== 0)
break;
if (n < 100)
{
int x = 0;
}
}
}
总结
1、归并排序(MERGE-SORT) 是建立在归并操作上的一种有效的排序算法，该算法是采用分治法(Divide and Conquer) (分治可以理解为递归) 的一个非常典型的应用。将有序的子序列进行合并得到完全有序的序列；即先使每个子序列有序，再使得子序列段间有序。
若将两个有序的子序列合并为一个有序的序列，称为二路归并；
2、外排序（External sorting）是能够处理极大数据量的排序算法；通常来说，外排序的数据不能一次性全部装入内存之中，只能放在读写较慢的外存储器之中(eg.硬盘)。外排序通常采用的是一种“排序 - 归并” 的策略。首先会将大文件中的数据分为多个部分读入内存中进行排序，当这些数据在内存中完成排序之后就会放到临时文件之中，然后依次进行，将待排序的数据组织为多个有序的临时文件。然后再归并阶段将这些临时文件组合成为一个大的有序的文件，即排序结果；