目录
前言
本章主要讲解：
归并外排序的操作以及实现（C语言）
注：本章需要用到文件操作的知识，如果有问题，可以先浏览学习一下文件操作的知识：?? C语言进阶 ?? 文件操作超详解【 建议关注+收藏 】
外排序
背景
? 一般提到排序都是指内排序，比如快速排序，堆排序，归并排序等。所谓内排序就是可以在内存中完成的排序，内存的访问速度大约是磁盘的25万倍，如果可以的话在内存中排序是非常快的。但对于大量数据来说，数据太大而无法全部都将数据加载到内存中，这时候就需要外排序。
概念
? 外排序指的是大文件的排序，即待排序的记录存储在外存储器上，待排序的文件无法一次装入内存，需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的。
归并外排序
在整体外排序中用归并的思想实现
- 排序策略
- 首先将整体大文件进行划分成多个内存能全加载的临时文件
- 再逐个对划分好的临时文件进行加载到内存，并进行内排序（可以使用高效的排序，建议快排）
- 排序好后对两两文件进行归并操作
- 具体归并细节：排升序
? 分别读取两两文件中的一个数据，进行比较，将小的数据输出到新的临时文件中，再对小数据的文件进行读取新的数据，以此循环直到归并完毕
- 图示过程：
- 实现代码：
//归并外排序
void Mergefile(const char* fin1, const char* fin2, const char* fmerge)
{
//以写入的方式创建合并后的新临时文件
FILE* fout = fopen(fmerge, "w");
if (fout == NULL)
{
perror("fopen fout fail\n");
exit(-1);
}
//以读取的方式打开合并子文件
FILE* file1 = fopen(fin1, "r");
if (file1 == NULL)
{
perror("fopen file1 fail\n");
exit(-1);
}
FILE* file2 = fopen(fin2, "r");
if (file2 == NULL)
{
perror("fopen file2 fail\n");
exit(-1);
}
//归并排序文件数据
int num1, num2;
int ret1 = fscanf(file1, "%d\n", &num1);//文件成功读取，读取指针则自动往后走
int ret2 = fscanf(file2, "%d\n", &num2);//所以保存返回结果，比较数据写入后再读取文件
while (ret1 != EOF && ret2 != EOF)
{
if (num1 < num2)
{
//写入数据并读取下一个数据
fprintf(fout, "%d\n", num1);
ret1 = fscanf(file1, "%d\n", &num1);
}
else
{
fprintf(fout, "%d\n", num2);
ret2 = fscanf(file2, "%d\n", &num2);
}
}
while (ret1 != EOF)
{
fprintf(fout, "%d\n", num1);
ret1 = fscanf(file1, "%d\n", &num1);
}
while (ret2 != EOF)
{
fprintf(fout, "%d\n", num2);
ret2 = fscanf(file2, "%d\n", &num2);
}
fclose(file1);
fclose(file2);
fclose(fout);
}
void MergeSortFile(const char* file, int N, int Num)
{
//以读取的方式打开数据文件
FILE* fout = fopen(file, "r");
if (fout == NULL)
{
perror("fopen fail\n");
exit(-1);
}
//开辟额外空间来接收数据
int* arr = malloc(sizeof(int) * Num);
if (arr == NULL)
{
perror("malloc fail\n");
exit(-1);
}
//把大文件划分成小文件，并排序
char subfile[100];//小文件名
int filei = 1, i=0, num;
while(fscanf(fout, "%d\n", &num) != EOF)
{
if (i < Num - 1)
{
arr[i++] = num;//载入内存
}
else//再入够数据进行排序，对排序好的数据输出到临时文件中
{
arr[i] = num;
QuickSort(arr, 0, Num-1);//排序
//排好后写入文件
sprintf(subfile, "Sortedfile%d", filei++);//创建修改小文件名
FILE* fin = fopen(subfile, "w");//以写入的方式创建小文件
if (fin == NULL)//文件开辟失败
{
perror("fopen subfile fail\n");
exit(-1);
}
//输出到文件中
for (int j = 0; j < Num; j++)
{
fprintf(fin, "%d\n", arr[j]);//写入排好的数据
}
fclose(fin);
i = 0;//更新记录读取数据的个数变量
}
}
//开始进行合并数据文件
char fin1[100] = "Sortedfile1";
char fin2[100] = "Sortedfile2";
char fmerge[100] = "Sortedfile12";
for (i = 1; i < N; i++)
{
//归并文件
Mergefile(fin1, fin2, fmerge);
//更替文件名
strcpy(fin1, fmerge);
sprintf(fin2, "Sortedfile%d", i + 2);
sprintf(fmerge, "%s%d", fmerge, i + 2);
}
fclose(fout);
free(arr);
}测试
- 测试代码：
int main()
{
//获取随机种子
srand(time(0));
//创建待排序数据文件
char file[100] = "datafile.txt";
FILE* data = fopen(file, "w");
if (data == NULL)
{
perror("fopen fail\n");
exit(-1);
}
//将随机数写进写入文件
const n = 10, num = 5000;
for (int i = 0; i < n * num; i++)
{
fprintf(data, "%d\n", rand());
}
fclose(data);
//排序
MergeSortFile(file, n, num);
return 0;
}- 测试结果：
?
?看来归并外排序实现的还是非常成功的！！