基数排序临时数组bucket

课题要求

随机生成100000个10000以内的随机数并使用基数排序记录排序时间

代码展示

#define N 100000
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
void sort(int a[N],int k)
{
      int temp[N]; //临时数组
      int i, bucket[10];
      for(i=0; i<10; ++i)
            bucket[i] = 0;//初始化桶（见本站基数排序Radix_sort）
      for (i = 0; i < N; i++)
          bucket[ (a[i]/k)%10 ]++;//a[i]/k)%10用于取每个数的各个位数
      for (i = 1; i < 10; i++)
          bucket[i] += bucket[i - 1];//计算所有桶，用于找到其处于临时数组的位置
      for (i = N - 1; i >= 0; i--)//逆序输出，与排序方式有关（先进先出）
      {
          temp[bucket[ (a[i]/k)%10 ] - 1] = a[i];//数组从零开始所以减一
          bucket[ (a[i]/k)%10 ]--;//出一减一
      }
      for (i = 0; i <N; i++)
         a[i] = temp[i];//将临时数组放回原始数组（进行5次）
}
void radix_sort(int a[N])
{
	int i,k;
	for(k=1;k<=10000;k*= 10)//跟据10000以内可得循环5次
		sort(a,k);
}
int main()
{
	int a[N],i;
	clock_t x,y;
	srand(time(0));//以当前时间随机生成整数
	for(i=0;i<N;i++)
		a[i]=rand()%10000;//取余控制随机数在0~10000以内
	x=clock();
	radix_sort(a);//基数排序（稳定排序直到循环结束才能完成排序）
	y=clock();
	for(i=0;i<N;i++)
		printf("%d ",a[i]);
	printf("\n运行时间：%f ms\n",(float)(y-x));//clock_t类强制转换为float计算时间差
	return 0;
}