m_sort.cpp

常用算法代码

#include <iostream.h>


void merge( int a[], int p, int q, int r, int m)
{
   int *bp=new int[m];
   int i,j,k;
   i=p;j=q+1;k=0;
   while (i<=q&&j<=r)
     {
	if (a[i]<=a[j])
	   bp[k++]=a[i++];
	else
	   bp[k++]=a[j++];
     }
   if (i==q+1)
      while (j<=r)
	  bp[k++]=a[j++];
   else
      while (i<=q)
	 bp[k++]=a[i++];
   for (i=p,k=0;i<=r;i++,k++)
     a[i]=bp[k];
   delete bp;
   }


template <class type>
void merge_sort(type a[], int n)
{
	int i,s,t=1;
    while (t<n)
	{
		s=t;
		t=2*s;
		i=0;
		while (i+t<n)
		{
			merge(a,i,i+s-1,i+t-1,t);
			i=i+t;
		}
		if (i+s<n)
			merge(a,i,i+s-1,n-1,n-i);
	}
}

int main()
{
	int a[]={8,5,3,9,11,6,4,1,10,7,2};
	merge_sort(a,11);
	for (int i=0;i<11;i++)
		cout<<a[i]<<" ";
	cout<<endl;
	return 0;
}