目录
本章主要讲解:
归并外排序的操作以及实现(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;
}
看来归并外排序实现的还是非常成功的!!