首页 > 代码库 > 基数排序算法
基数排序算法
基数排序（Radix sort）是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。基数排序的发明可以追溯到1887年赫尔曼·何乐礼在打孔卡片制表机（Tabulation Machine）上的贡献。
它是这样实现的：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。LSD的基数排序适用于位数小的数列，如果位数多的话，使用MSD的效率会比较好。MSD的方式与LSD相反，是由高位数为基底开始进行分配，但在分配之后并不马上合并回一个数组中，而是在每个“桶子”中建立“子桶”，将每个桶子中的数值按照下一数位的值分配到“子桶”中。在进行完最低位数的分配后再合并回单一的数组中。
本文地址：http://www.cnblogs.com/archimedes/p/radix-sort-algorithm.html，转载请注明源地址。
举例
第一步
第二步
第三步
算法实现
// Completed on 2014.10.10 21:10// Language: C99//// 版权所有（C）codingwu (mail: oskernel@126.com) // 博客地址：http://www.cnblogs.com/archimedes/#include<stdio.h>#include<stdlib.h>int maxbit(int data[], int n) //辅助函数，求数据的最大位数{ int d = 1; //保存最大的位数 int p = 10; for(int i = 0; i < n; ++i) { while(data[i] >= p) { p *= 10; ++d; } } return d;}void radixsort(int data[], int n) //基数排序{ int d = maxbit(data, n); //数组中的元素的最大位数 int *tmp = (int *)malloc(n * sizeof(int)); int *count = (int *)malloc(10 * sizeof(int)); //计数器 int 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 < n; j++) { k = (data[j] / radix) % 10; //计算每次循环某一位的数字 count[k]++; //统计每个桶中的记录数 } for(j = 1; j < 10; j++) count[j] = count[j - 1] + count[j]; //第j个桶以及之前所有桶中元素的总数 for(j = n - 1; j >= 0; j--) { //将所有桶中记录依次收集到tmp中 k = (data[j] / radix) % 10; tmp[count[k] - 1] = data[j]; count[k]--; } for(j = 0; j < n; j++) //将临时数组的内容复制到data中 data[j] = tmp[j]; radix = radix * 10; } free(tmp); free(count);}int main(){ int a[] = {288, 52, 123, 30, 212, 23, 10, 233}; int n; n = sizeof(a) / sizeof(a[0]); radixsort(a, n); for(int k = 0; k < n; k++) printf("%d ", a[k]); printf("\n"); return 0;}
效率分析
时间效率：设待排序列为n个记录，d个关键码，关键码的取值范围为radix，则进行链式基数排序的时间复杂度为O(d(n+radix))，其中，一趟分配时间复杂度为O(n)，一趟收集时间复杂度为O(radix)，共进行d趟分配和收集。
空间效率：需要2*radix个指向队列的辅助空间，以及用于静态链表的n个指针。
基数排序算法