mergesort.cpp

是一本教程的实例代码,可以下载后直接运行,即可以得到答案.

#include <iostream.h>                    //归并排序

const int N=10;
void output(int table[],int n);

void onemerge(int x[],int y[],int m,int r,int n1)   //一次归并
{                                //将x中相邻的两个子序列归并到y中
    int i=m,j=r,k=m;
    while(i<r && j<r+n1 && j<N)
    { 
        cout<<x[i]<<"<"<<x[j]<<"? ";
        if(x[i]<x[j])
        {                                //较小的值送到y中
            y[k]=x[i];
            k++;
            i++;
        }
        else
        {
            y[k]=x[j];
            k++;
            j++;
        }
    }
    while(i<r)                         //将前一子序列余下的值复制到y中
    {
        y[k]=x[i];
        k++;
        i++;
    }
    while(j<r+n1 && j<N)                //将后一子序列余下的值复制到y中
    {
        y[k]=x[j];
        k++;
        j++;
    }
}

void mergepass(int x[],int y[],int len)  //一趟归并排序
{                                        //将x中元素归并到y中
    int i=0,j;
    cout<<"len="<<len<<"  ";
    while (i<=N-2*len)
    {
        onemerge(x,y,i,i+len,len);
        i=i+2*len;
    }
    cout<<" i="<<i<<" i+len="<<i+len<<"  ";
    if (i+len<N)
        onemerge(x,y,i,i+len,len);       //再一次归并
    else  
        for(j=i;j<N;j++)                 //将x中余下的值复制到y中
            y[j]=x[j];
}

void mergesort(int x[])                  //归并排序算法
{
    int len=1;                           //已排序的序列长度,初始值为1
    int temp[N];                         //temp所需空间与x一样
    do
    {
        mergepass(x,temp,len);           //将x中元素归并到temp中
        output(temp,N);
        len=len*2;
        mergepass(temp,x,len);           //将temp中元素归并到x中
        output(x,N);
        len=len*2;
    } while(len<N);
}

void main()
{
    int a[N]={8,3,2,7,9,1,6,5,0,4};
    cout<<"N="<<N;
    output(a,N);
    mergesort(a);
}
/*程序运行结果 ：
N=10	 table: 8 3 2 7 9 1 6 5 0 4 
len=1  8<3? 2<7? 9<1? 6<5? 0<4?  i=10 i+len=11  	 table: 3 8 2 7 1 9 5 6 0 4 
len=2  3<2? 3<7? 8<7? 1<5? 9<5? 9<6?  i=8 i+len=10  	 table: 2 3 7 8 1 5 6 9 0 4 
len=4  2<1? 2<5? 3<5? 7<5? 7<6? 7<9? 8<9?  i=8 i+len=12  table: 1 2 3 5 6 7 8 9 0 4 
len=8   i=0 i+len=8  1<0? 1<4? 2<4? 3<4? 5<4? 	 	 table: 0 1 2 3 4 5 6 7 8 9 
*/

void output(int table[],int n)               //输出数组的n个元素
{
    cout<<"\t table: ";
    for(int i=0;i<n;i++)
        cout<<table[i]<<" ";
    cout<<"\n";
}