锐客网

  1. 首页 > it技术 > >

基数排序(RadixSortC语言)

算法



#include
#include
#include
int getMax(int arr[], int n);
void countSort(int arr[], int n, int exp);
void countSort(int arr[], int n, int exp);
void radix_sort(int arr[], int n);
void print(int arr[], int n);
int * buildarray(void);
#define ARRAYSIZE 2000000




int main()
{
【基数排序(RadixSortC语言)】int * arr=buildarray();
print(arr,ARRAYSIZE);
float time_start=clock();
radix_sort(arr, ARRAYSIZE);
float time_end=clock();
print(arr, ARRAYSIZE);
printf("Consume :%.2fs",(time_end-time_start)/CLOCKS_PER_SEC);
free(arr);
}






// 获取 arr[]中的最大数
int getMax(int arr[], int n)
{
int mx = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > mx)
mx = arr[i];
return mx;
}


// 据exp所代表的位
// 使用低位计数排序
void countSort(int arr[], int n, int exp)
{
int output[n]; // 输出数组
int i;
int count[10] = {0};
// 将相应位的数字记录在count[]数组中
for (i = 0; i < n; i++)
count[ (arr[i]/exp)%10 ]++;
// count［i］实际上表示
//各个数在output[]所在的位置
for (i = 1; i < 10; i++)
count[i] += count[i - 1];
// 建立输出数组
for (i = n - 1; i >= 0; i--)
{
output[count[ (arr[i]/exp)%10 ]-1 ] = arr[i];
count[ (arr[i]/exp)%10 ]--;
}


// 复制output到arr[]中， 因此 arr[] 中
// 实际上按目前位排序后的结果
for (i = 0; i < n; i++)
arr[i] = output[i];
}


// main() 函数里面用到的radix_sort()函数
void radix_sort(int arr[], int n)
{
//找到最大数，以此来确定有多少位
int m = getMax(arr, n);


// 此处有一定技巧，也是最出彩的地方（个人看法），不是依靠人传递位，而是通过
// 下面这个式子，来确定各个位上的值
for (int exp = 1; m/exp > 0; exp *= 10)
countSort(arr, n, exp);
}


// 打印数组
void print(int arr[], int n)
{
for (int i = 0; i < n; i++)
{printf("%5d",arr[i]);
if((i+1)%10==0)
putchar('\n');
}
putchar('\n');
}


//建立数组
int * buildarray(void)
{int * arr=(int *)malloc(ARRAYSIZE*sizeof(int));
srand(time(0));
for(int i=0; i
arr[i]=rand()%ARRAYSIZE;
return arr;
}


    推荐阅读


    上一篇：快手春招笔试题（后端研发）第二题机器人

    下一篇：centos虚拟机克隆 网卡配置