文件中海量数据的排序

文件中海量数据的排序

题目：

跟之前堆排序可以解决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这个文件中