排序算法之基数排序，随机数的产生和程序运行时间的计算
一，基数排序
基本思想：
按最低位优先法先对低位关键字进行排序，直到对最高位关键字排序为止，经过若干次分配和收集来实现排序
基数排序中用到了箱排序，每个箱子都是先进先出，因此采用队列是最合理的数据结构。如下图：
开始采用顺序表的存储结构，每次分派10个Length长的队列，写了很多代码，运行却发现速度很慢，不符合基数排序的理论时间复杂度O（k*n），而且消耗内存也很多(10*n).找了原因可能是自己写的队列影响了速度，因此采用了以数组做存储结构，只分配n的长度，设一个计数标志数组记录存储位置。
二，随机数产生
首先调用srand（（int）time（NULL））函数，设定随机数种子。返回的随机数（确切地说是伪随机数）实际上都是根据递推公式计算的一组数值，当序列足够长，这组数值近似满足均匀分布。先调用srand初始化，一般用当前日历时间初始化随机数种子，这样每次执行代码都可以产生不同的随机数。
函数rand()可以生成0—RAND_MAX（）之间的一个随机数，其中RAND_MAX 是stdlib.h 中定义的一个整数，它与系统有关。测试系统值RAND_MAX为32767，可以编写自己的库函数更改，由于本系统重在序列个数多少，和整数大小范围关系不大，因此没有在系统中实现。
本系统编写了一个随机产生low和high之间的整数：int RandomInteger(int low,int high)
其中产生low和high之间的函数语句：k=(long)(rand()%(high-low+1)+low);
三，时间函数
clock_t start, finish;
double duration;
start = clock();
radixsort(L,10000);
finish = clock();
duration = (double)(finish - start) / CLOCKS_PER_SEC;
——————————————
代码分界线———————————————————————————
#include<stdio.h>
#include<malloc.h>
#include <stdlib.h>
#include<time.h>
//辅助函数，求数据的最大位数
int maxbit(int L[],int n) {
int d = 1,i=0; //保存最大的位数
int p=10;
for(i = 0;i < n; i++) {
while(L[i] >= p) {
p *= 10;
d++;
}
}
return d;
}
//基数排序
void radixsort(int L[],int len) {
int d = maxbit(L,len);
long * tmp = (long *)malloc(len*sizeof(long));
long * count = (long *)malloc(10*sizeof(long));; //计数器,10个桶
long i,j,k;
int radix = 1;
for(i = 1; i <= d; i++)
{ //进行d次排序
for(j = 0; j < 10;j++) //每次分配前清空计数器
count[j] = 0;
for(j = 0;j < len; j++)
{ //统计每个桶中的记录数
k = (L[j]/radix)%10;
count[k]++;
}
for(j = 1;j < 10; j++) //将tmp中的位置依次分配给每个桶
count[j] = count[j-1] + count[j];
for(j = len-1;j >= 0;j--)
{ //将所有桶中记录依次收集到tmp中
k = (L[j]/radix)%10;
count[k]--;
tmp[count[k]] = L[j];
}
for(j = 0;j < len;j++) //将临时数组的内容复制到L中
L[j] = tmp[j];
radix = radix*10;
}
free(tmp);
free(count);
}
int RandomInteger(long low,long high)
{
long k;
k=(long)(rand()%(high-low+1)+low);
return k;
}
int main()
{
long i=0;
long * L = (long *)malloc(10000*sizeof(long));
clock_t start, finish;
double duration;
srand( (long)time( NULL ) );
for(i=0;i<10000;i++)
{
L[i]=i;//RandomInteger(0,10000);
}
start = clock();
radixsort(L,10000);
finish = clock();
duration = (double)(finish - start) / CLOCKS_PER_SEC;
for(i=0;i<10000;i++)
{
printf("%7.2ld ",L[i]);
}
printf("%5.4lfs ",duration);
getchar();
getchar();
getchar();
return 0;
}
creat by 张飞雪
补充：软件开发 , 其他 ,
