C++ 归并排序算法

C++ 归并排序算法

//Merge sort 
//programming by : Erfan Nasoori
//Email : ketn68@yahoo.com
//Date of sent : 2009/1/21
#include<iostream.h>
#include<math.h>
//function declaration
void merge(int[],int[],int[],int,int); // MERGE sort function
void bubblesortAsce(int[],int);        // ASCENDING sort function
void bubblesortDesce(int[],int);       // DESCENDING sort function
void main()
{
 int a[100],b[100],c[200],m,n,s,i;
 char key;
 cout<<"Well come to merge sort program of C++ ."<<endl;
do{
        cout<<endl;
        cout<<"~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"<<endl;
	cout<<"How many number do you need for array a?"<< endl;
	cout<<"m=";   cin>>m;
	cout<<"Now please enter m numbers in array a :"<<endl;
	for(i=0;i<m;++i)
	 {
	  cout<<"element["<<(i+1)<<"]=";
	  cin>>a[i];
	 }
	bubblesortAsce(a,m);
	cout<<"a ASCENDING sorted is:"<<endl;
	for(i=0;i<m;++i)
	 {
	  cout<<" "<<a[i]<<" ";
	 }
	cout<<endl;
	cout<<"~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"<<endl;
	cout<<"How many number do you need for array b?"<<endl;
	cout<<"n=";   cin>>n;
	cout<<"Now please enter n numbers in array b :"<<endl;
	for(i=0;i<n;++i)
	 {
	  cout<<"element["<<(i+1)<<"]=";
	  cin>>b[i];
	 }
        bubblesortDesce(b,n);
        cout<<"b DESCENDING sorted is:"<<endl;
        for(i=0;i<n;++i)
	 {
	  cout<<" "<<b[i]<<" ";
	 }
        cout<<endl;
        cout<<"~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"<<endl;
        cout<<"array c is merged array."<<endl;
        merge(a,b,c,m,n);
        for(i=0;i<m+n;++i)
	{
	 cout<<" "<<c[i]<<" ";
	}
        cout<<endl;
        cout<<"~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"<<endl;
        cout<<"\n\nDo you want to continue to work by program?"<<endl;
        cout<<"If you want it press y ,whereas press any key."<<endl;
        cin>>key;
 }
 while(key=='y' || key=='Y');
}
//function implementation/////////////////////
void bubblesortAsce(int x[],int y)
{
int i,j,hold;
for(i=1;i<=y-1;++i)
 for(j=0;j<y-i;++j)
 {
  if(x[j] > x[j+1])
  {
    hold=x[j];
    x[j]=x[j+1];
    x[j+1]=hold;
  }
 }
}
//function implementation/////////////////////
void bubblesortDesce(int z[],int w)
{
 int i,j,hold;
 for(i=1;i<=w-1;++i)
  for(j=0;j<w-i;++j)
  {
    if(z[j] < z[j+1])
    {
      hold=z[j];
      z[j]=z[j+1];
      z[j+1]=hold;
    }
  }
}
//function implementation/////////////////////
void merge(int x[],int z[],int ME[],int y,int w)
{
 int i,j,l,s;
 s=w+y;
 for(i=0,j=w-1,l=0 ; i<y && j>=0 ;     )
  if(x[i]<z[j])
  {
    ME[l]=x[i];
    ++i;
    ++l;
  }
  else
  {
    ME[l]=z[j];
    --j;
    ++l;
  }
 if(y>w)
  for(; i<y;++i,l++)
   ME[l]=x[i];
 else
  for(; j>=0; l++,--j)
   ME[l]=z[j];
}