利用随机函数产生30000个随机整数，利用所学的排序方法进行排序，并统计每一种排序上机所花费的时间

Answer 1

#include "stdio.h"
#include "time.h"
#include "malloc.h"
#include "stdlib.h"
void insert(int *a,int n) //插入
{
int i,j,temp;
for(i=1;i<n;i++) {
temp=a[i]; /*temp为要插入的元素*/
j=i-1;
while(j>=0&&temp<a[j]) { /*从a[i-1]开始找比a[i]小的数，同时把数组元素向后移*/
a[j+1]=a[j];
j--;
}
a[j+1]=temp; /*插入*/
}
}

void bubble(int *a,int n) /*定义两个参数：数组首地址与数组大小*/
//冒泡
{
int i,j,temp;
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++) /*注意循环的上下限*/
if(a[i]>a[j])
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}

void selectsort(int *a,int n) //选择排序
{
int i,j,k,temp;
for(i=0;i<n-1;i++) {
k=i; /*给记号赋值*/
for(j=i+1;j<n;j++)
if(a[k]>a[j]) k=j; /*是k总是指向最小元素*/
if(i!=k) { /*当k!=i是才交换，否则a[i]即为最小*/
temp=a[i];
a[i]=a[k];
a[k]=temp;
}
}
}

void quick(int *a,int i,int j) //快排
{
int m,n,temp;
int k;
m=i;
n=j;
k=a[(i+j)/2]; /*选取的参照*/
do {
while(a[m]<k&&m<j) m++; /* 从左到右找比k大的元素*/
while(a[n]>k&&n>i) n--; /* 从右到左找比k小的元素*/
if(m<=n) { /*若找到且满足条件，则交换*/
temp=a[m];
a[m]=a[n];
a[n]=temp;
m++;
n--;
}
}while(m<=n);
if(m<j) quick(a,m,j); /*运用递归*/
if(n>i) quick(a,i,n);
}

void merge(int a[],int low,int middle,int high)
{
int h,i,j,k;
int b[30000];
h=low;
i=low;
j=middle+1;

while(h<=middle&&j<=high)
{
if(a[h]<=a[j])
{
b[i]=a[h];
h++;
}
else
{
b[i]=a[j];
j++;
}
i++;
}
if(h>middle)
for(k=j;k<=high;k++)
{
b[i]=a[k];
i++;
}
else
{
for(k=h;k<=middle;k++)
{
b[i]=a[k];
i++;
}
}
for(k=low;k<=high;k++)
{
a[k]=b[k];
}
}

//归并排序函数的具体实现
void mergesort(int a[],int low,int high)
{
int middle;
if(low<high)
{
middle=(low+high)/2;
mergesort(a,low,middle);
mergesort(a,middle+1,high);
merge(a,low,middle,high);
}
}

int main()
{
srand(time(NULL));
int i,a[30000],n=30000;
float start,end; // 开始时间,结束时间

for( i=0;i<30000;i++)
a[i]=rand()%50000;
start=(float)clock();
insert(a,30000);
end=(float)clock();
printf("插入排序时间是:%.f毫秒\n",end-start);

for( i=0;i<30000;i++)
a[i]=rand()%50000;
start=(float)clock();
bubble(a,30000);
end=(float)clock();
printf("冒泡排序时间是:%.f毫秒\n",(end-start));

for( i=0;i<30000;i++)
a[i]=rand()%50000;
start=(float)clock();
selectsort(a,30000);
end=(float)clock();
printf("选择排序时间是:%.f毫秒\n",(end-start));

for( i=0;i<30000;i++)
a[i]=rand()%50000;
start=(float)clock();
quick(a,0,n-1);
end=(float)clock();
printf("快速排序时间是:%.f毫秒\n",(end-start));

for( i=0;i<30000;i++)
a[i]=rand()%50000;
start=(float)clock();
mergesort(a,0,n-1);
end=(float)clock();
printf("归并排序时间是:%.f毫秒\n",(end-start));

return 0;
}

Answer 2

如果随机范围不大可用计数排序...