alexp11.c

来自「1、 字符串由随机产生的1~16位的字母组成」· C语言 代码 · 共 202 行

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>
#include<windows.h>
#include<math.h>
/*------------------------------------------------------------*/
void INSERTSORT(char**str1,int length)
{                                      //插入排序
   int i,j;
   char*key;
   for(i=2;i<length+1;i++)
   {
	   key=str1[i];
	   j=i-1;
	   while((j>0)&&((strcmp(str1[j],key)>0)))
	   {
		   
		   str1[j+1]=str1[j];
		   j--;
	   }
	   str1[j+1]=key;
   }
}
/*------------------------------------------------------------*/
void BUBBLESORT(char** str1,int length)
{                                   //冒泡排序
   int i,j;
   char *temp;
   for(i=1;i<length+1;i++)
   {
	   for(j=1;j<length+1-i;j++)
	   {
		   if(strcmp(str1[j],str1[j+1])>0)
		   {
			   temp=str1[j];
			   str1[j]=str1[j+1];
			   str1[j+1]=temp;
		   }
	   }
   }
}        
/*------------------------------------------------------------*/
void MAXHEAP(char** str,int m,int length) 
{                               //最大化堆
	char *temp;
	int largest;
	if((2*m<length+1)&&(strcmp(str[2*m],str[m])>0)) largest=2*m;
	else largest=m;
	if((2*m+1<length+1)&&(strcmp(str[2*m+1],str[largest])>0)) largest=2*m+1;
	if(largest!=m)
	{
		temp=str[largest];
		str[largest]=str[m];
		str[m]=temp;
		MAXHEAP(str,largest,length);
	}
}
/*------------------------------------------------------------*/
void BUILDMAXHEAP(char** str,int length)
{                               //建最大堆
	int m;
	for(m=(int)length/2;m>0;m--)MAXHEAP(str,m,length);
}
/*------------------------------------------------------------*/
void HEAPSORT(char** str,int length)
{                               //堆排序
	int i;
	char *temp;
	BUILDMAXHEAP(str,length);
	for (i=length;i>1;i--)
	{
		temp=str[1];
		str[1]=str[i];
		str[i]=temp;
		MAXHEAP(str,1,i-1);
	}
}
/*------------------------------------------------------------*/
void MERGE(char** str,int p,int q,int r)
{                               //归并算法
	int m,n,i,j,k;
	char **lstr,**rstr;
	m=q-p+1;
	n=r-q;
	lstr=(char**)malloc((m+2)*sizeof(char*));
	rstr=(char**)malloc((n+2)*sizeof(char*));
	for(i=1;i<m+1;i++)lstr[i]=str[p+i-1];
	for(j=1;j<n+1;j++)rstr[j]=str[q+j];
	lstr[m+1]="{";
	rstr[m+1]="{";
	i=1;j=1;
	for(k=p;k<r+1;k++)
	{
		if(strcmp(lstr[i],rstr[j])>0)
		{
			str[k]=rstr[j];
			j++;
		}
		else
		{
			str[k]=lstr[i];
			i++;
		}
	}
}
/*------------------------------------------------------------*/
void MERGESORT(char** str,int p,int r)
{                                 //归并排序
	int q;
	if(p<r)
	{
		q=(int)floor((p+r)/2);
		MERGESORT(str,p,q);
		MERGESORT(str,q+1,r);
		MERGE(str,p,q,r);
	}
}
/*------------------------------------------------------------*/
int PARTITION(char** str,int p,int r)
{                                 //快排划分
	char *x,*temp;
	int i,j;
	x=str[r];
	i=p-1;
	for(j=p;j<r;j++)
	{
		if((strcmp(x,str[j])>0)||(strcmp(x,str[j])==0))
		{
			i++;
			temp=str[j];
			str[j]=str[i];
			str[i]=temp;
		}
	}
	temp=str[j];
	str[j]=str[i+1];
	str[i+1]=temp;
	return i+1;
}
/*------------------------------------------------------------*/
void QUICKSORT(char **str,int p,int r)
{                                   //快速排序
	if(p<r)
	{
		int q;
		q=PARTITION(str,p,r);
		QUICKSORT(str,p,q-1);
		QUICKSORT(str,q+1,r);
	}
}
/*------------------------------------------------------------*/
main()
{   
	int i,j,lenw,lenl,a;
	char** str;
	char* str1;
	LARGE_INTEGER time1;
    LONGLONG begin,end;
	printf("请输入2的指数次：");
	scanf("%d",&a);
	printf("\n");
    lenw=(int)pow(2,a);
	str=(char**)malloc((lenw+1)*sizeof(char*));
	srand(time(NULL));
    for(i=1;i<lenw+1;i++)
	{
	    lenl=rand()%16+1;
		str1=(char*)malloc((lenl+1)*sizeof(char));
		for(j=0;j<lenl;j++)str1[j]=(char)((rand()%26)+97);
		str1[j]='\0';
		str[i]=str1;
	}
	printf("1、插入排序;\n2、冒泡排序；\n3、堆排序；\n4、归并排序;\n5、快速排序;\n请选择排序算法的种类：");
	scanf("%d",&a);
	printf("\n");
	QueryPerformanceCounter(&time1);
    begin=time1.QuadPart;
	switch(a)
	{
    case 1:INSERTSORT(str,lenw);break;
	case 2:BUBBLESORT(str,lenw);break;
	case 3:HEAPSORT(str,lenw);break;
	case 4:MERGESORT(str,1,lenw);break;
	case 5:QUICKSORT(str,1,lenw);break;
	default:printf("\nERROR\n");
	}
    QueryPerformanceCounter(&time1);
    end=time1.QuadPart;
//	for(i=1;i<lenw+1;i++)printf("%s\n",str[i]);
	//printf("ok\n");
	printf("程序运行的时间为%e ms\n",(double)(end-begin));
}
/*LARGE_INTEGER time1;
LONGLONG begin,end;
QueryPerformanceCounter(&time1);
begin=time1.QuadPart;
INSERT_SORT(integ1,n);
QueryPerformanceCounter(&time1);
end=time1.QuadPart;
cout<<"the RUNNINGTIME of INSERT_SORT"<<"  "<<(double)(end-begin)<<endl;)*/