integer_sort.cpp

一 ：排序n个元素

#include   <stdlib.h>   
#include   <stdio.h>   
#include   <time.h> 
#include   <iostream.h>
#include   <fstream.h>
#include  <math.h>
                  //10    12       14    16     18      20
#define  M 4096  //1024，4096，16384，65536，262144，1048576
#define  N 10000


  void random( int a[M])   
 {   
     int i;
	 int b;

     srand(   (unsigned)time(   NULL   )   );   
    
        
	 for(i=0;i<M;i++)
	 {b=rand();
	   if (b<N&&b>0)
		{  a[i]=b; 
//		   cout<<a[i]<<" ";
		 }
		else i--;
		   
	  }
	 cout<<endl;
}

/*插入排序*/
  void insertion_sort( int b[M])
{
  int i,j,key;
 
  for(j=1;j<M;j++)
  { 
	 key=b[j];
     i=j-1; 
	 while(i>=0&&b[i]>key)
	 { 
	   b[i+1]=b[i];
	   i=i-1;
	 }
	 b[i+1]=key;
  }
}

/*快速排序*/

int  partition (int a[M],int p,int r)
{  
	int x=a[r],i=p-1,j,key;
	for(j=p;j<=r-1;j++)
		if(a[j]<=x)
		{
			i=i+1;
			key=a[i];a[i]=a[j];a[j]=key;
		}
     key=a[i+1];a[i+1]=a[r];a[r]=key;
	 return(i+1);
}
    
void quick_sort(int a[M],int p,int r)
{
	int q;
	if(p<r)
	{	q=partition(a,p,r);
		quick_sort(a,p,q-1);
		quick_sort(a,q+1,r);
	}
}
	



/*计数排序*/
void counting_sort(int a[M],int b[M])
{
	int i,j;
    int *c=new int[N+1];
	for(i=0;i<=N;i++)	c[i]=0;
	for(j=0;j<M;j++)	c[a[j]]=c[a[j]]+1;
	for(i=1;i<=N;i++)   c[i]=c[i]+c[i-1];
	for(j=M-1;j>=0;j--)  
	{
		b[c[a[j]]-1]=a[j];
	    c[a[j]]=c[a[j]]-1;
	}
	delete c;
}



/*基数排序*/
void radix_sort(int a[M])
{
	int i,j;
	int d=10;
	int *e=new int[M];
	int *f=new int[M];
	for(i=0;i<5;i++)
	{
		for(j=0;j<M;j++)
		{	e[j]=a[j]%d; a[j]=a[j]/10;}
	counting_sort(e,f);
	}
    delete e;
	delete f;
}



/*合并排序*/
void merge(int a[M],int p,int q,int r)
{
	int n1,n2,i,j,k;
	n1=q-p+1;
	n2=r-q;
	//int L[M];
	int *L=new int [n1+1];
	//int R[M];
	int *R=new int [n2+1];
	for(i=0;i<n1;i++)  L[i]=a[p+i];
	for(j=0;j<n2;j++)  R[j]=a[q+j+1];
	L[n1]= N+5  ;  R[n2]=N+5 ;
	i=0;
	j=0;
	for(k=p;k<=r;k++)
	{
	 if (L[i]<=R[j])
		{a[k]=L[i];
	     i=i+1;
		}
	  else 
		{a[k]=R[j];
	    j=j+1;
		}	
	}
	delete L;
	delete R;
}

void  merge_sort(int a[M],int p,int r)
{   int q;
	if(p<r)
	{
		q=(p+r)/2;
	    merge_sort(a,p,q);
        merge_sort(a,q+1,r);
        merge(a,p,q,r);
	}
}




 void main()
 {  
   int i;
   ifstream indate;
   ofstream outdate;
   outdate.open("d:\\time.txt");
   int *b=new int [M];
   int *d=new int [M];
   int *a=new int [M];
   clock_t   t1,t2;   
    
   random(a); 

//	for(i=0;i<M;i++)   cout<<a[i]<<"  ";
//  cout<<"\n";

	for(i=0;i<M;i++)   d[i]=a[i];    //插入排序
	t1=clock();
	insertion_sort(d);
	t2=clock();
	cout<<"insertion_sort排序时间为:";
	cout<<t2-t1<<"ms"<<endl;
   
	outdate<<"insertion_sort排序时间为:";
    outdate<<t2-t1<<"ms"<<endl;
//	for(i=0;i<M;i++)  cout<<d[i]<<"  ";
//	cout<<"\n";

	for(i=0;i<M;i++)   d[i]=a[i];    //快速排序
	t1=clock();
	quick_sort(d,0,M-1);
	t2=clock();
	cout<<"quick_sort排序时间为:";
    cout<<t2-t1<<"ms"<<endl;
    outdate<<"quick_sort排序时间为:";

	outdate<<t2-t1<<"ms"<<endl;
    

	for(i=0;i<M;i++)   d[i]=a[i];  //计数排序
	t1=clock();
    counting_sort(d,b);
	t2=clock();
	cout<<"counting_sort排序时间为:";
	cout<<t2-t1<<"ms"<<endl;
	
	outdate<<"counting_sort排序时间为:";
	outdate<<t2-t1<<"ms"<<endl;
  
	for(i=0;i<M;i++)   d[i]=a[i];   //基数排序
	t1=clock();
    radix_sort(d);
	t2=clock();
	cout<<"radix_sort排序时间为:";
	cout<<t2-t1<<"ms"<<endl;
    
	outdate<<"radix_sort排序时间为:";
	outdate<<t2-t1<<"ms"<<endl;
	
	for(i=0;i<M;i++)   d[i]=a[i];  
	t1=clock();
    merge_sort(d,1,M-1);
	t2=clock();
	cout<<"merge_sort排序时间为:";
	cout<<t2-t1<<"ms"<<endl;
    
	
    delete a;
    delete d;
    delete b;
	outdate.close();
	
 }