排序总体来说分为两类,数据在内存中的叫做内排序,数据存在磁盘的叫外排序。
一般而言,磁盘中存放的都是大型数据,所以,外排序主要是应用于磁盘中大型数据的。
一.排序思想
对于外排序而言,因为待排的数据往往远大于内存容量,所以在排序时通常将数据切分,切分成能在内存中排序的大小,将分成的小块依次在内存中排好序后按归并的思路进行整合即可。
我们这里举例子说话:
假设我们有一组100G的数据,已知内存最多存放20G,那么我们把这100G的数据切分成5份,每份20G。
将每份数据排序后依次放入新创建的文档中。
注意:此时所有的数据依旧存放在磁盘中。
将第一、二个文档归并排序,数据依次录入新创建的文档。
将存有40G的文档与第三个文档归并排序,同时依次录入新创建的文档。
按这样进行直到最后一个小文档也被归并完成。
外排序结束。
值得注意的是,所有的数据均是被存放在了磁盘中,只有在进行数据间的归并排序和最初小磁盘排序时是在内存中进行。
二.代码实现
实现外排序,需要一定的文件操作知识,希望大家先自己尝试实现它,这样更有利于能力的提升。
void Cut_FileData(const char* filename);
void MergeSort_File(const char* file1, const char* file2, const char* filemix);
void main()
{
Cut_FileData("总文件路径");
//进行小份数据之间的归并
char file1[100] = "小文件1路径";
char file2[100] = "小文件2路径";
char filemix[100] = "第一次合并后文件路径";
for (int i = 0; i < 4; i++)//总共份数减一次归并
{
MergeSort_File(file1, file2, filemix);
sprintf(file2, "D:\\git all\\file%d.txt", i + 3);
memcpy(file1, filemix, sizeof(char) * 100);
if(i < 1)
sprintf(filemix, "第%d次合并后文件路径.txt", i + 2);
else
sprintf(filemix, "最终排序完成文件路径");
}
}
void Cut_FileData(const char* filename)
{
FILE* fileorg = fopen(filename, "r");
if (fileorg == NULL) cout << "fileorg failure\n";
int gap = 20;//总共有100个数据,分成5份,每份20个数据
for (int i = 0; i < 5; i++)//分成5小份
{
int n = 0;
vector<int> arr;
while (n++ < 20)
{
int num = 0;
fscanf(fileorg, "%d\n", &num);
arr.push_back(num);
}
sort(arr.begin(), arr.end());
char min_filename[100] = "1";//创建每一小份的文件数据
sprintf(min_filename, "第%d小份文件.txt", i + 1);
FILE* newfile = fopen(min_filename, "w");
if (newfile == NULL)
{
cout << "newfile failure\n";
exit(-1);
}
for (auto x : arr)
{
fprintf(newfile, "%d\n", x);
}
fclose(newfile);
}
fclose(fileorg);
}
void MergeSort_File(const char* file1, const char* file2, const char* filemix)
{
FILE* filea = fopen(file1, "r");
if (filea == NULL)
{
cout << "filea failure\n";
exit(-1);
}
FILE* fileb = fopen(file2, "r");
if (fileb == NULL)
{
cout << "fileb failure\n";
exit(-1);
}
FILE* filesum = fopen(filemix, "w");
if (filesum == NULL)
{
cout << "filesum failure\n";
exit(-1);
}
int num1 = 0, num2 = 0;
int ret1 = fscanf(filea, "%d\n", &num1);
int ret2 = fscanf(fileb, "%d\n", &num2);
while (ret1 != EOF && ret2 != EOF)//读取文件相当于归并往前走一位, 所以每比较一次就只需要让入数据的小磁盘读取下一个数据即可
{
if (num1 <= num2)
{
fprintf(filesum, "%d\n", num1);
ret1 = fscanf(filea, "%d\n", &num1);
}
else
{
fprintf(filesum, "%d\n", num2);
ret2 = fscanf(fileb, "%d\n", &num2);
}
}
while (ret1 != EOF)
{
fprintf(filesum, "%d\n", num1);
ret1 = fscanf(filea, "%d\n", &num1);
}
while (ret2 != EOF)
{
fprintf(filesum, "%d\n", num2);
ret2 = fscanf(fileb, "%d\n", &num2);
}
fclose(filea);
fclose(fileb);
fclose(filesum);
}
创作不易,麻烦三连支持一下吧
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)