外部排序之文件归并

2024-09-02 06:36

文章标签 归并排序外部

本文主要是介绍外部排序之文件归并，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

概述

外部排序（External Sorting）是一种用于处理无法完全加载到内存中的大量数据的排序技术。由于内存的限制，传统的内存排序算法（如快速排序、归并排序）可能无法处理超大规模的数据集合。因此，需要采用外部排序技术，将数据分割成较小的块，利用磁盘进行排序。

文件归并

概念

文件归并（File Merging）是一种将多个已排序文件合并成一个单一排序文件的过程。这通常用于处理大规模数据集，其中数据已经被分割成多个部分，每部分在内存中排序后存储在磁盘上。

实现思路

（1）读取n个值排序后写入file1，再读取n个值排序后写入file2

（2）file1和file2利用归并排序的思想，依次读取比较，取小的数尾插到mfile，mfile再归并为一个有序文件
在这里插入图片描述
（3）重命名mfile为file1，再次从data中读取n个数据排序后写入file2
（4）重复步骤2、3直到data无法读出数据，得到排序好的文件file1

代码实现

#include<stdio.h>
#include<time.h>
#include<stdlib.h>
//创建随机数据
void CreateDate()
{int n = 40000;//生成随机数据（自1970年1月1日）srand(time(0));//常量字符指针 用file存储文件名的字符串const char* file = "data.txt";//对file文件进行写操作FILE* fin = fopen(file, "w");if (fin == NULL){perror("fopen error");//打印错误信息return;}//生成n个随机数并写入文件for (int i = 0; i < n; i++){int x = rand() + i;//添加换行符——保持数据完整性,方便读入fscanffprintf(fin, "%d\n", x);}fclose(fin);
}int compare(const void* a, const void* b)
{return (*(int*)a - *(int*)b);
}//传入file的实参，无需每次打开file文件，直接读出n个数据到file1
int ReadNDateSortToFile(FILE* fout,int n,const char* file1)
{//创建空间为n的数组int* a = (int*)malloc(sizeof(int) * n);if (a == NULL){perror("malloc fail");return 0;}int x = 0;//如果遇到文件读取结束，实际读取的数据为j个int j = 0;for (int i = 0; i < n; i++){//从fout读出一个数据赋值给x//如果读不出来说明data中数据读取完成if (fscanf(fout, "%d", &x) == EOF)break;a[j++] = x;}if (j == 0){free(a);return 0;}//内部排序（随意选择一种排序方法）qsort(a, j, sizeof(int), compare);//对file1文件进行写操作FILE* fin = fopen(file1, "w");if (fin == NULL){perror("fopen error");//打印错误信息return 0;}for (int i = 0; i < j; i++){fprintf(fin, "%d\n", a[i]);}free(a);fclose(fin);return j;//返回实际读到的数据个数，没有数据了返回0
}void MergeFile(const char* file1, const char* file2, const char* mfile)
{FILE* fout1 = fopen(file1, "r");if (fout1 == NULL){perror("fopen error");//打印错误信息return;}FILE* fout2 = fopen(file2, "r");if (fout2 == NULL){perror("fopen error");//打印错误信息return;}FILE* mfin = fopen(mfile, "w");if (mfin == NULL){perror("fopen error");//打印错误信息return;}//归并操作int x1 = 0;int x2 = 0;int ret1 = fscanf(fout1, "%d\n", &x1);int ret2 = fscanf(fout2, "%d\n", &x2);while (ret1 != EOF && ret2 != EOF){if (x1 < x2){fprintf(mfin, "%d\n", x1);ret1 = fscanf(fout1, "%d\n", &x1);}else{fprintf(mfin, "%d\n", x2);ret2 = fscanf(fout2, "%d\n", &x2);}}while (ret1 != EOF){fprintf(mfin, "%d\n", x1);ret1 = fscanf(fout1, "%d\n", &x1);}while (ret2 != EOF){fprintf(mfin, "%d\n", x2);ret2 = fscanf(fout2, "%d\n", &x2);}fclose(fout1);fclose(fout2);fclose(mfin);
}int main()
{CreateDate();const char* file1 = "file1.txt";const char* file2 = "file2.txt";const char* mfile = "mfile.txt";//对fout文件进行写操作FILE* fout = fopen("data.txt", "r");if (fout == NULL){perror("fopen error");//打印错误信息return 0;}ReadNDateSortToFile(fout,100,file1);ReadNDateSortToFile(fout, 100, file2);//文件归并while (1){MergeFile(file1, file2, mfile);//删除file1和file2remove(file1);remove(file2);//重命名mfile为file1rename(mfile, file1);//读入100个数据排序后到file2if (ReadNDateSortToFile(fout, 100, file2) == 0)break;}return 0;
}