多路归并的外排序

算法 | 2008-06-10 09:57:28 | 阅读 23297 次 | 评论(1)
  //多路归并的外排序

    //思路如下:
    //1.按各输入文件中下一个读到的元素的大小构造一个输入流最小堆.
    //2.从堆顶文件里读一个元素并写入输出文件.
    //3.同时按读的那个文件的下一个元素的值调整堆.
    //4.若第3步已到达文件结尾.则从堆中删除该输入流
    //5 如果堆中还有元素. 回到第2步

#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#include<iterator>
#include<functional>
using namespace std;

    //这个类主要用来管理一个输入流.
    //它知道流中还有没有元素.
    //可以查看下一个将读出来的元素的值.
    //可以读出一个元素.
    template <class T>
    class Yudu {
    private:
        istream & _istream;
        T _next;
        bool _have_next;
    public:
        Yudu( istream & x) : _istream(x) {
            if (_istream &gt;&gt; _next) _have_next = true;
            else _have_next = false;
        }
        inline bool have_next() { return _have_next; }
        //读出流中下一个元素
        T read_next() {  
            if (! _have_next) {
                cout <&lt; "读取错误! 退出" &lt;&lt; endl;
                exit(1);
            }
            T temp = _next;
            if (_istream >&gt; _next)
                _have_next = true;
            else
                _have_next = false;
            return temp;
        }
        //看看下一个元素但不读出来
        inline const T& look_next() const { return _next; }
    };

    //比较两个Yudu对象下一个元素的大小
    //提供给paixu函数中的堆操作时使用
    class bijiao
    {
    public:
        template <typename T>
        bool operator() (const Yudu<T>* a, const Yudu<T>* b) {
            return a-&gt;look_next() &gt; b-&gt;look_next() ;
        }
    };

    //文件排序函数
    template <typename T>
    void paixu(vector<Yudu&lt;T>* &gt;& v , ostream& out){
        //先删除数组中的"没有下一个元素"的Yudu对象.例如一个空的文件构造的Yudu对象.
        v.erase( remove_if(v.begin(),v.end(),
            not1(mem_fun(& Yudu<T>::have_next))), v.end() );
        make_heap(v.begin(), v.end(), bijiao());
        while (! v.empty() ){
            pop_heap(v.begin(),v.end(), bijiao());
            out <&lt; v.back()->read_next() <&lt; " ";   // out 以文本方式打开. 如果是其它方式这里要改.
            if (! v.back()->have_next() )
                v.pop_back();
            else
                push_heap(v.begin(), v.end(), bijiao());
        }
    }
    int main() {
        ifstream in[3];
        in[0].open("1.txt");
        in[1].open("2.txt");
        in[2].open("3.txt");
        vector<Yudu&lt;int>* &gt; v;
        v.push_back(new Yudu<int>(in[0])); //实际使用时要释放new出的对象.或者用boost的智能指针.
        v.push_back(new Yudu<int>(in[1]));
        v.push_back(new Yudu<int>(in[2]));
        ofstream o("out.txt");
        paixu(v, o);
        cin.get();
        return 0;
    }
    /*
    测试(三个文件中是已经有序的数)
    1.txt:  1 5 9 12 21
    2.txt:  3 4 5 7 8
    3.txt:  2 3 5 10 11 14 19 25 27
    执行归并后
    out.txt:
    1 2 3 3 4 5 5 5 7 8 9 10 11 12 14 19 21 25 27
    */
文章评论,共1条
vfdff(作者)
2008-06-10 10:01
1
一、思路描述:<br />
&nbsp;&nbsp;&nbsp; 设两个有序的子文件(相当于输入堆)放在同一向量中相邻的位置上:R[low..m],R[m+1..high],先将它们合并到一个局部的暂存向量R1(相当于输出堆)中,待合并完成后将R1复制回R[low..high]中。<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<br />
&nbsp;&nbsp;&nbsp; 二路归并排序的过程是:<br />
&nbsp;&nbsp;&nbsp; (1)把无序表中的每一个元素都看作是一个有序表,则有n个有序子表;<br />
&nbsp;&nbsp;&nbsp; (2)把n个有序子表按相邻位置分成若干对(若n为奇数,则最后一个子表单独作为一组),每对中的两个子表进行归并,归并后子表数减少一半;<br />
&nbsp;&nbsp;&nbsp; (3)反复进行这一过程,直到归并为一个有序表为止。<br />
<br />
&nbsp;&nbsp;&nbsp; 二路归并排序过程的核心操作是将一维数组中相邻的两个有序表归并为一个有序表。<br />
<br />
二、分类:<br />
&nbsp;&nbsp;&nbsp; 归并排序可分为:多路归并排序、两路归并排序 。<br />
&nbsp;&nbsp;&nbsp; 若归并的有序表有两个,叫做二路归并。一般地,若归并的有序表有k个,则称为k路归并。二路归并最为简单和常用,既适用于内部排序,也适用于外部排序,本文只讨论二路归并。<br />
<br />
三、算法分析: <br />
&nbsp;&nbsp;&nbsp; 1、稳定性:归并排序是一种稳定的排序。<br />
<br />
&nbsp;&nbsp;&nbsp; 2、存储结构要求:可用顺序存储结构。也易于在链表上实现。<br />
<br />
&nbsp;&nbsp;&nbsp; 3、时间复杂度: 对长度为n的文件,需进行lgn趟二路归并,每趟归并的时间为O(n),故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlgn)。。<br />
<br />
&nbsp;&nbsp;&nbsp; 4、空间复杂度:需要一个辅助向量来暂存两有序子文件归并的结果,故其辅助空间复杂度为O(n),显然它不是就地排序。<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 注意:若用单链表做存储结构,很容易给出就地的归并排序。<br />
&nbsp;&nbsp;&nbsp; <br />
&nbsp;&nbsp;&nbsp; 总结:与快速排序相比,归并排序的最大特点是,它是一种稳定的排序方法。归并排序一般多用于外排序。但它在内排方面也占有重要地位,因为它是基于比较的时间复杂度为O(N*Log(N))的排序算法中唯一稳定的排序,所以在需要稳定内排序时通常会选择归并排序。归并排序不要求对序列可以很快地进行随机访问,所以在链表排序的实现中很受欢迎。<br />
<br />
<br />
四、算法描述(C语言)<br />
/*<br />
* Last edit 2007.12.9,hkmgjsf@yahoo.com.cn ,KnowMore<br />
*/<br />
#include <br />
#include <br />
#include <br />
#define DATA_SIZE 10<br />
void sort(int *iData, int n);<br />
void puts_a( int iData[],int n );<br />
void MergePass( int R[],int length,int n );<br />
void merge (int R[], int low, int m, int heigh);<br />
main()<br />
{<br />
&nbsp;&nbsp;&nbsp; int i,iData[DATA_SIZE];<br />
&nbsp;&nbsp;&nbsp; printf( &quot;\nplease input %d numbers:\n&quot;,DATA_SIZE );<br />
&nbsp;&nbsp;&nbsp; for( i=0;i&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; scanf( &quot;%d&quot;,&amp;iData[i] );<br />
&nbsp;&nbsp;&nbsp; sort( iData,DATA_SIZE );<br />
&nbsp;&nbsp;&nbsp; printf( &quot;sorts complete:\n&quot; );<br />
&nbsp;&nbsp;&nbsp; puts_a( iData,DATA_SIZE );<br />
}<br />
<br />
void sort( int *iData,int n )<br />
{<br />
&nbsp;&nbsp;&nbsp;/*对比两个有序子序列大小,并合并为新的有序列<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 5&nbsp;&nbsp;3 6&nbsp;&nbsp;5 5&nbsp;&nbsp;4 8&nbsp;&nbsp;7 9<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;35&nbsp;&nbsp;&nbsp;56&nbsp;&nbsp;&nbsp;45&nbsp;&nbsp;&nbsp;78&nbsp;&nbsp;9<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 3556&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;4578&nbsp;&nbsp;&nbsp;9<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;34555678&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;9<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;345556789*/<br />
&nbsp;&nbsp;&nbsp;int i;/*子表表长*/<br />
&nbsp;&nbsp;&nbsp;for( i=1;i&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;MergePass( iData,i,n );/* 有序段长度≥n时终止 */<br />
<br />
<br />
}<br />
<br />
void MergePass( int R[],int length,int n )<br />
{<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/* 对R[1..n]做一趟归并排序 */<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int i;<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for(i=0;i+2*length-1&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;merge(R,i,i+length-1,i+2*length-1);<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/* 归并长度为length的两个相邻子文件 */<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(i+length-1&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;merge(R,i,i+length-1,n-1); /* 归并最后两个子文件 */<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/* 注意:若i≤n且i+length-1≥n时,则剩余一个子文件轮空,无须归并 */<br />
<br />
}<br />
<br />
<br />
/*<br />
 *归并两个有序数组<br />
*/<br />
void merge (int R[], int low, int m, int heigh)<br />
{<br />
&nbsp;&nbsp;&nbsp; int i = low, j = m+1, p = 0;<br />
&nbsp;&nbsp;&nbsp; int *R1;<br />
<br />
&nbsp;&nbsp;&nbsp; R1=( int * )malloc( sizeof(int)*(heigh-low+1) );<br />
&nbsp;&nbsp;&nbsp; assert( R1 != NULL );/*断言,内存分配成功*/<br />
<br />
&nbsp;&nbsp;&nbsp; printf( &quot;low=%d\tm=%d\theigh=%d\n&quot;,low,m,heigh );<br />
<br />
&nbsp;&nbsp;&nbsp; while( i&lt;=m &amp;&amp; j&lt;=heigh )<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;R1[p++]=( R[i] <br />
<br />
&nbsp;&nbsp;&nbsp; /* puts_a( R,DATA_SIZE ); */<br />
&nbsp;&nbsp;&nbsp; /* printf(&quot;-----left merge---------\n&quot;); */<br />
&nbsp;&nbsp;&nbsp; while( i&lt;=m )<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;R1[p++]=R[i++];<br />
&nbsp;&nbsp;&nbsp; /* puts_a( R,DATA_SIZE ); */<br />
&nbsp;&nbsp;&nbsp; /* printf(&quot;-----right merge---------\n&quot;); */<br />
&nbsp;&nbsp;&nbsp; while( j&lt;=heigh )<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;R1[p++]=R[j++];<br />
&nbsp;&nbsp;&nbsp; /* puts_a( R,DATA_SIZE ); */<br />
&nbsp;&nbsp;&nbsp; /* printf(&quot;-----Copy---------\n&quot;); */<br />
&nbsp;&nbsp;&nbsp; for( p=0,i=low;i&lt;=heigh;i++,p++ )<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;R[i]=R1[p];<br />
<br />
&nbsp;&nbsp;&nbsp; /* puts_a( R,DATA_SIZE ); */<br />
<br />
}<br />
<br />
void puts_a( int iData[],int n )<br />
{<br />
&nbsp;&nbsp;&nbsp; int i;<br />
&nbsp;&nbsp;&nbsp; for( i=0;i&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; printf( &quot;%d\t&quot;,iData[i] );<br />
&nbsp;&nbsp;&nbsp; printf(&quot;\n&quot;);<br />
&nbsp;&nbsp;&nbsp; getch();<br />
}
游客请输入验证码
浏览1861238次