alexp2.c

1、 字符串由随机产生的1~16位的字母组成

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<math.h>
#include<windows.h>
/*------------------------------------------------------------*/
void INSERTSORT(int*str1,int length)
{                                      //插入排序
   int i,j;
   int key;
   for(i=2;i<length+1;i++)
   {
	   key=str1[i];
	   j=i-1;
	   while((j>0)&&(str1[j]>key))
	   {
		   
		   str1[j+1]=str1[j];
		   j--;
	   }
	   str1[j+1]=key;
   }
}
/*------------------------------------------------------------*/
int PARTITION(int* str,int p,int r)
{                                 //快排划分
	int x,temp;
	int i,j;
	x=str[r];
	i=p-1;
	for(j=p;j<r;j++)
	{
		if((x>str[j])||(x==str[j]))
		{
			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(int*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);
	}
}
/*------------------------------------------------------------*/
void COUNTINGSORT(int*str,int len)
{                                   //计数排序
	int c[10001];
	int i,*b;
	b=(int*)malloc((len+1)*sizeof(int));
	for(i=0;i<10001;i++)c[i]=0;
	for(i=1;i<len+1;i++)c[str[i]]=c[str[i]]+1;
	for(i=1;i<10001;i++)c[i]=c[i-1]+c[i];
	for(i=len;i>0;i--)
	{
		b[c[str[i]]]=str[i];
		c[str[i]]=c[str[i]]-1;
	}
	for(i=1;i<len+1;i++)str[i]=b[i];
}
/*------------------------------------------------------------*/
void COUNTINGSORT1(int*str,int len,int k)
{                                   //基数排序中的计数排序
	int c[10];
	int i,*b;
	b=(int*)malloc((len+1)*sizeof(int));
	for(i=0;i<10;i++)c[i]=0;
	for(i=1;i<len+1;i++)c[(((int)(str[i]/k))%10)]=c[(((int)(str[i]/k))%10)]+1;
	for(i=1;i<10;i++)c[i]=c[i-1]+c[i];
	 for(i=len;i>0;i--)
	{
		b[c[(((int)(str[i]/k))%10)]]=str[i];
		c[(((int)(str[i]/k))%10)]=c[(((int)(str[i]/k))%10)]-1;
	}
	for(i=1;i<len+1;i++)str[i]=b[i];
}
/*------------------------------------------------------------*/
void RADIXSORT(int*str,int len)
{                                    //基数排序
	int i;
	for(i=1;i<10001;i=i*10)COUNTINGSORT1(str,len,i);
}
/*------------------------------------------------------------*/
main()
{   
	int i,len,a;
	int *str;
    LARGE_INTEGER time1;
    LONGLONG begin,end;
	//while(c)
	//{
	printf("请输入2的指数次：");
	scanf("%d",&a);
	printf("\n");
    len=(int)pow(2,a);
	str=(int*)malloc((len+1)*sizeof(int));
	srand(time(NULL));
    for(i=1;i<len+1;i++)str[i]=rand()%10000+1;
	printf("1、插入排序;\n2、快速排序；\n3、计数排序；\n4、基数排序;\n请选择排序算法的种类：");
	scanf("%d",&a);
	printf("\n");
	QueryPerformanceCounter(&time1);
    begin=time1.QuadPart;
	switch(a)
	{
	case 1:INSERTSORT(str,len);break;
	case 2:QUICKSORT(str,1,len);break;
	case 3:COUNTINGSORT(str,len);break;
	case 4:RADIXSORT(str,len);break;
	default:printf("\nERROR\n");
	}
	QueryPerformanceCounter(&time1);
    end=time1.QuadPart;
	//for(i=1;i<len+1;i++)printf("%d ",str[i]);
	//printf("ok\n");
	printf("程序运行的时间为%e ms\n",(double)(end-begin));
	//printf("是否继续:");
	//scanf("%d",&c);
	//printf("\n");
	//}
}