string_sort.cpp

本程序实现了各种对字符串的排序,学习算法的同志看过来!

#include   <stdlib.h>   
#include   <stdio.h>   
#include   <time.h> 
#include   <iostream.h>
#include  <math.h>
#include<string.h>
                      //10    11    12    13   14       15    16     17       18     19       20
#define   M  131072  //1024，2048，4096，8192，16384，32768，65536，131072，262144，524288，1048576
#define   N  16


void  random_string(char a[M][N+1])
{
   int i,j,k;  
   const char CCH[] = "abcdefghijklmnopqrstuvwxyz";//ABCDEFGHIJKLMNOPQRSTUVWXYZ";
   srand(   (unsigned)time(   NULL   )  );   
   for(j=0;j<M;j++)
   { //  w=rand();
      // if (w>16)   w=w%16;
	   for ( i = 0; i < N; i++)
		{
        k= rand() % (sizeof(CCH) - 1);  
        a[j][i] = CCH[k];
		}
	 
      a[j][N]='\0';
	 }
  // for(j=0;j<M;j++)   cout<<a[j]<<endl;
   
}


/*插入排序*/
void insertion_sort( char b[M][N+1])
{
  int i,j;
  char	key[N+1];
  for(j=1;j<M;j++)
  { 
	 strcpy(key,b[j]);
     i=j-1; 
	 while(i>=0&&strcmp(key,b[i])<0)
	 { 
	   strcpy(b[i+1],b[i]);
	   i--;
	 }
	 strcpy(b[i+1],key);
  }
}
/*冒泡排序*/
void increase_sort(char a[M][N+1])
{
	int i,j;
	char key[N+1];
	for(i=0;i<M-1;i++)
		for(j=M-1;j>i;j--)
			if(strcmp(a[j],a[j-1])<0)
			{strcpy(key,a[j]);   strcpy(a[j],a[j-1]);  strcpy(a[j-1],key);}
}

/*快速排序*/
int  partition (char a[M][N+1],int p,int r)
{  
	int i=p-1,j;
	char x[N+1],key[N+1];
    strcpy(x,a[r]);
	for(j=p;j<=r-1;j++)
		if(strcmp(a[j],x)<=0)
		{
			i++;
			strcpy(key,a[i]);   strcpy(a[i],a[j]);  strcpy(a[j],key);	
		}
   	strcpy( key,a[i+1]);  strcpy(a[i+1],a[r]);   strcpy(a[r],key);
	 return(i+1);
}
    
void quick_sort(char a[M][N+1],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 merge(char a[M][N+1],int p,int q,int r)
{
	int n1,n2,i,j,k;
	n1=q-p+1;
	n2=r-q;
 // char L[M][N+1];
  //char R[M][N+1];
   char(*L)[N+1]=new char [n1+1][N+1];
   char(*R)[N+1]=new char [n2+1][N+1];
	for(i=0;i<n1;i++)  strcpy(L[i],a[p+i]);
	for(j=0;j<n2;j++)  strcpy(R[j],a[q+j+1]);
	strcpy(L[n1],"zzzzzzzzzzzzzzz~");
	strcpy(R[n2],"zzzzzzzzzzzzzzz~");
	i=0;  j=0;
	for(k=p;k<=r;k++)
	{
	 if (strcmp(L[i],R[j])<=0)
		{strcpy(a[k],L[i]);
	     i=i+1;
		}
	  else 
		{strcpy(a[k],R[j]);
	    j=j+1;
		}	
	}
	delete []L;
	delete []R;

}

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


/*堆排序*/
int parent(int i)
{
	return (i-1)/2;
}

int left(int i)
{
	return 2*i+1;
}

int right(int i)
{
	return 2*i+2;
}

void min_heapify(char a[M][N+1],int i,int n)
{
	int l=left(i);
	int r=right(i);
	int smallest;
    char key[N+1];
	if(l<n && strcmp(a[l],a[i])<0)  smallest=l;
	   else smallest=i;
	if(r<n && strcmp(a[r],a[i])<0)  smallest=r;
	if(smallest!=i)
	{
		strcpy(key,a[i]);   strcpy(a[i],a[smallest]);  strcpy(a[smallest],key);	
		min_heapify(a,smallest,M);
	}
}
void build_min_heapify(char a[M][N+1])
{
	int i;
	for(i=(M-2)/2;i>=0;i--)
		min_heapify(a,i,M);
}
void heap_sort(char a[M][N+1])
{   
	char key[N+1];
	int k=M;
	int i;
	build_min_heapify(a);
	for(i=(k-2)/2;i>=0;i--)
	{
		strcpy(key,a[0]);   strcpy(a[0],a[i]);  strcpy(a[i],key);
		k--;
		min_heapify(a,1,k);
	}
}



void main()
 {  
   int i;
   char(*a)[N+1]=new char [M][N+1];
   char(*b)[N+1]=new char [M][N+1];
   clock_t   t1,t2;   

   random_string(a);

   for(i=0;i<M;i++) strcpy(b[i],a[i]);     //插入排序
   t1=clock();
   insertion_sort(b);
   t2=clock();
   cout<<"insertion_sort排序时间为:";
   cout<<t2-t1<<"ms"<<endl;
  // for(i=0;i<M;i++)  cout<<b[i]<<endl;
   
   for(i=0;i<M;i++) strcpy(b[i],a[i]);     //冒泡排序
   t1=clock();
   increase_sort(b);
   t2=clock();
   cout<<"increase_sort排序时间为:";
   cout<<t2-t1<<"ms"<<endl;
   
   
   for(i=0;i<M;i++) strcpy(b[i],a[i]);       //快速排序
   t1=clock();
   quick_sort(b,0,M-1);
   t2=clock();
   cout<<"quick_sort排序时间为:";
   cout<<t2-t1<<"ms"<<endl;

  
   for(i=0;i<M;i++) strcpy(b[i],a[i]);       //归并排序
   t1=clock();
   merge_sort(b,0,M-1);
   t2=clock();
   cout<<"merge_sort排序时间为:";
   cout<<t2-t1<<"ms"<<endl;
   

   for(i=0;i<M;i++) strcpy(b[i],a[i]);       //堆排序
   t1=clock();
   heap_sort(b);
   t2=clock();
   cout<<"heap_sort排序时间为:";
   cout<<t2-t1<<"ms"<<endl;
 //  for(i=0;i<M;i++)  cout<<b[i]<<endl;
   

   delete []a;
   delete []b;

}