merg_sort.cpp

常见算法

//create a cataloge includea array[]
#include<iostream>
using namespace std;


#define M 20
int theArray[M];
int arrayB[M];
int*pa=0,*pb=0;
main()
{

	int i,j,k=0;
	
	pb=arrayB;
	pa=theArray;
	void sort(int st,int ed);
	void combine(int a,int b,int c);


    cout<<"input  "<<M<<" numbers:"<<endl;
	for(i=0;i<M;i++)
	cin>>theArray[i];
	cout<<"the array is:\n";
    for(i=0,j=1;i<M;i++,j++)
	{
			cout<<theArray[i]<<"\t";
			if(j%5==0)
				cout<<endl;
	}
	cout<<endl;

	sort(pa,0,M-1);
	cout<<"the inline array is:"<<endl;
	pb=arrayB;
	for(i=0,j=1;i<M;i++,j++)
	{
			cout<<*pb<<"\t";
			if(j%5==0)
				cout<<endl;
			pb++;
	}
	cout<<endl;
	return 0;
}
void sort(int st,int ed)
{
	int min;
	if(st<ed)
	{
	min=(ed+st)/2;
	sort(pa,st,min);
	sort(pa,min+1,ed);
	combine(pa,st,min,ed);
	}

}
void combine(int a,int b,int c)
{
	
		int i,j;
        pa=&theArray[a];
		if(a==c)
		{
			*pb=*pa;
		     pb++;
		}
		else if(b==c)
		{
			if(*pa>theArray[b])
			{
				*pb=theArray[b];
				pb++;
			}
			else
			{
				*pb=*pa;
				pb++;
			}
		}
		else
		{

        
		   for(i=a,j=b+1;i<=b&&j<=c;)
		   {
			
			if(*pa>theArray[j])
			{
				*pb=theArray[j];

				j++;pb++;
			}
			else
			{
				*pb=*pa;
				pa++;
			    i++;pb++;
			}
			if(i>b&&j<=c)
			{
				for(;j<=c;)
				{
				*pb=theArray[j];
				j++;pb++;
				}
			}
			if(i<=b&&j>c)
			{
				for(;i<=b;)
				{
                *pb=theArray[i];
			    i++;pb++;
				}
			}
		   }
		}
}