一，基数排序
基本思想：
按最低位优先法先对低位关键字进行排序，直到对最高位关键字排序为止，经过若干次分配和收集来实现排序
基数排序中用到了箱排序，每个箱子都是先进先出，因此采用队列是最合理的数据结构。如下图：
开始采用顺序表的存储结构，每次分派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;
}