归并排序
外部排序
一、定义问题
外部排序指的是大文件的排序，即待排序的记录存储在外存储器上，待排序的文件无法一次装入内存，需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的。外部排序最常用的算法是多路归并排序，即将原文件分解成多个能够一次性装入内存的部分，分别把每一部分调入内存完成排序。然后，对已经排序的子文件进行多路归并排序。
二、处理过程
按可用内存的大小，把外存上含有n个记录的文件分成若干个长度为L的子文件，把这些子文件依次读入内存，并利用有效的内部排序方法对它们进行排序，再将排序后得到的有序子文件重新写入外存；
对这些有序子文件逐趟归并，使其逐渐由小到大，直至得到整个有序文件为止。
三、示例
假设有两个存储了有序数列的文件：source1.txt和source2.txt，以及一个存入排序结果的destination.txt文件。
source1.txt文件存储内容如下所示：
source2.txt文件存储内容如下所示：
归并（Merge）操作将两个有序数列合并为一个新的有序数列。其过程大致是：从source1中取出最小的元素x，从source2取出最小的元素y，比较x和y的大小，将较小的数存入destination文件，如果该值为x，则取source1中紧邻x的下一个数值与y比较，以此类推。下面是一个简单的代码实现：
[cpp] view plaincopyprint?//将字符串转变为int型变量
int str2int(string str)
{
int ret=0;
for(int i=0;i!=str.length();++i)
ret=ret*10 + str[i]-'0';
return ret;
}
int main()
{
ifstream fsource1;
ifstream fsource2;
ofstream fdestination;
fsource1.open("source1.txt");
fsource2.open("source2.txt");
fdestination.open("destination.txt");
if(!fsource1 || !fsource1 ||!fdestination)
{
cout<<"打开文件失败！";
return;
}
string str1;
string str2;
int num1=0;
int num2=0;
fsource1>>str1;
fsource2>>str2;
while(fsource1 || fsource2)
{
if(fsource1 && fsource2)
{
num1 = str2int(str1);
num2 = str2int(str2);
if(num1<=num2)
{
fdestination<<num1<<" ";
fsource1>>str1;
}
else
{
fdestination<<num2<<" ";
fsource2>>str2;
}
}
else if(fsource1)
{
fdestination<<str1<<" ";
fsource1>>str1;
}
else
{
fdestination<<str2<<" ";
fsource2>>str2;
}
}
return 0;
}
//将字符串转变为int型变量
int str2int(string str)
{
int ret=0;
for(int i=0;i!=str.length();++i)
ret=ret*10 + str[i]-'0';
return ret;
}
int main()
{
ifstream fsource1;
ifstream fsource2;
ofstream fdestination;
fsource1.open("source1.txt");
fsource2.open("source2.txt");
fdestination.open("destination.txt");
if(!fsource1 || !fsource1 ||!fdestination)
{
cout<<"打开文件失败！";
return;
}
string str1;
string str2;
int num1=0;
int num2=0;
fsource1>>str1;
fsource2>>str2;
while(fsource1 || fsource2)
{
if(fsource1 && fsource2)
{
num1 = str2int(str1);
num2 = str2int(str2);
if(num1<=num2)
{
fdestination<<num1<<" ";
fsource1>>str1;
}
else
{
fdestination<<num2<<" ";
&n
补充：软件开发 , C++ ,
