齐齐哈尔哪里做网站,手机网站对企业用户的好处,东莞网络游戏制作开发,平台搭建心得文件中海量数据的排序
题目#xff1a;
跟之前堆排序可以解决TopK问题一样#xff0c;我们来看看归并排序会用来解决什么问题#xff1f; 思路#xff1a;
我们说归并排序是外排序。其实就是将数据分成一个个小段#xff0c;在内存中进行排序#xff0c;再拿出内存
跟之前堆排序可以解决TopK问题一样我们来看看归并排序会用来解决什么问题 思路
我们说归并排序是外排序。其实就是将数据分成一个个小段在内存中进行排序再拿出内存在外部比如文件磁盘中进行归并排序。
其实就是数据量太大无法直接通过内存来排序我们将其平均切割成100份1000份等等比如将其切割成原数据切割成100份每份拿出来就可以放到内存中去排序排完之后放到一个个小文件中。
这样就会有100个小文件这100个小文件里面都是排序好的数据然后让文件去归并让上一个文件和下一个文件中的数据去归并最终实现的就是全部数据都放在一个文件里并且是有序的。
文件的合并思路如下图所示 文件归并的过程就是在文件中进行的就是在磁盘上进行的。这就是外排序 具体的归并思路
就是让两个文件归并后的文件跟下一个文件接着归并。 让file1 指向mfile文件file2指向下一个文件继续归并file1 和 file2文件生成mfile文件 然后就一直循环直至mfile文件和第 n 个文件归并后。就结束。
代码实现
void MergeFile(const char* file1, const char* file2, const char* mfile)
{// 打开file1 文件FILE* fout1 fopen(file1, r);if (fout1 NULL){perror(MergeFile():fopen:fout1);exit(-1);}// 打开file2文件FILE* fout2 fopen(file2, r);if (fout2 NULL){perror(MergeFile():fopen:fout2);exit(-1);}// 打开mfile文件准备写入。FILE* fin fopen(mfile, w);if (fin NULL){perror(MergeFile():fopen:fin);exit(-1);}// 将file1 和 file2的数据读出来归并到mfile文件中int num1, num2;int ret1 fscanf(fout1, %d\n, num1);int ret2 fscanf(fout2, %d\n, num2);while (ret1 ! EOF ret2 ! EOF) // 通过fscanf的返回值来判断是否有文件读取完毕{// 判断num1 和 num2 谁大谁小if (num1 num2){fprintf(fin, %d\n, num1); // 小的数据放到fin指向的文件ret1 fscanf(fout1, %d\n, num1);// 这一步是为了让文件指针 读取下一个数据}else{fprintf(fin, %d\n, num2);ret2 fscanf(fout2, %d\n, num2);}}// 走到这里有可能是fout1 或者是 fout2 文件先读取完// 要把剩下的进行处理while (ret1 ! EOF){fprintf(fin, %d\n, num1);ret1 fscanf(fout1, %d\n, num1);}while (ret2 ! EOF){fprintf(fin, %d\n, num2);ret2 fscanf(fout2, %d\n, num2);}// 关闭文件fclose(fout1);fclose(fout2);fclose(fin);
}void MergeSortFile(const char* file)
{// 读取传进来的file文件FILE* fout fopen(file, r);if (fout NULL){perror(fopen:fout);exit(-1);}// 读取文件中的数据 ,将其分割成多组在内存中进行排序再放入对应文件中int n 10; // 将文件中的数据切割成10个一组int num 0;int* a (int*)malloc(sizeof(int) * n); // 用于在内存中进行排序的数组int i 0;int filei 1; // 每组数据所存放的文件的下标char subfile[20]; // 用于存放各组数据文件的文件while (fscanf(fout, %d\n, num) ! EOF) // 从文件中读取数据写到num中 [读取失败返回EOF]{// 将读出来的数据放到一个数组中if (i n - 1) // 只读前n - 1个到数组中 第n个在else中处理{a[i] num;}else{// 走进循环fscanf还是读了一个数据到num上要记得处理a[i] num;// 走到这里说明已经把文件中的数据全部读取到数组a中// 对其进行快排QuickSort(a, 0, n - 1);// n - 1是最后一个元素的下标// 排序完之后我们将数据放回到文件中这里我们选择每一组数据都放进一个文件中sprintf(subfile, sub\\sub_sort%d.txt, filei); // 创建各个文件的名字FILE* fin fopen(subfile, w); // 打开subfile所记载的文件名如果没有由于是w形式 会自动创建一个if (fin NULL){perror(fopen:fin);exit(-1);}// 往文件里写,我们排好序的数组for (int j 0; j n; j){fprintf(fin, %d\n, a[j]);}fclose(fin);i 0; // 重置i}}// 现在文件中的数据 被我们分成了一组组个数为n的有序数据并放在了对应的文件中// 我们对这个文件进行归并排序。 也就是在磁盘上进行文件内数据的归并是外排序char mfile[100] 12;char file1[100] sub\\sub_sort1.txt;char file2[100];char subsortfile[100] subsortfile\\12; // 将归并后的mfile子文件都放到subsortfile文件中for (int i 2; i n; i){sprintf(file2, sub\\sub_sort%d.txt, i);// 读取file1 和 file2的数据 归并到subsortfile文件的mfile子文件中MergeFile(file1, file2, subsortfile);// 更新file1指向的文件名strcpy(file1, subsortfile);// 更新mfilesprintf(mfile, %s%d, mfile, i 1);// 更新subsortfile的mfile子文件名sprintf(subsortfile, subsortfile\\%s, mfile);}fclose(fout);
}测试效果如下
Sort是原数据存放的地方我们这里只放了小数据便于我们调试。 sub文件中 subsortfile文件中 最终的12345678910就是所有文件归并后的结果。
将一开始的Sort文件内的数据有序的存放在1234568910这个文件中
