当前位置:编程学习 > C/C++ >>

归并排序

外部排序
一、定义问题
外部排序指的是大文件的排序,即待排序的记录存储在外存储器上,待排序的文件无法一次装入内存,需要在内存和外部存储器之间进行多次数据交换,以达到排序整个文件的目的。外部排序最常用的算法是多路归并排序,即将原文件分解成多个能够一次性装入内存的部分,分别把每一部分调入内存完成排序。然后,对已经排序的子文件进行多路归并排序。
二、处理过程

按可用内存的大小,把外存上含有n个记录的文件分成若干个长度为L的子文件,把这些子文件依次读入内存,并利用有效的内部排序方法对它们进行排序,再将排序后得到的有序子文件重新写入外存;
对这些有序子文件逐趟归并,使其逐渐由小到大,直至得到整个有序文件为止。
三、示例
假设有两个存储了有序数列的文件:source1.txt和source2.txt,以及一个存入排序结果的destination.txt文件。
source1.txt文件存储内容如下所示:
source1
 

source2.txt文件存储内容如下所示:
source2
 

归并(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++ ,
CopyRight © 2012 站长网 编程知识问答 www.zzzyk.com All Rights Reserved
部份技术文章来自网络,