基本思想：
基数排序是一种有意思的排序，在看过其它比较排序后，基数排序真的很有意思。
基数排序(Radix Sort)属于分配式排序，又称"桶子法"(Bucket Sort或Bin Sort)，将要排序的元素分配到某些"桶"中，以达到排序的作用。基数排序属于稳定的排序，其时间复杂度为nlog(r)m (其中r为的采取的基数,m为堆数)，基数排序的效率有时候高于其它比较性排序。
基数排序的方式可以采用最低位优先LSD（Least sgnificant digital）法或最高位优先MSD（Most sgnificant digital）法，LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。LSD的基数排序适用于位数小的数列，如果位数多的话，使用MSD的效率会比较好，MSD的方式恰与LSD相反，是由高位数为基底开始进行分配，其他的演算方式则都相同。
以LSD为例，假设原来有一串数值如下所示：
73, 22, 93, 43, 55, 14, 28, 65, 39, 81
首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中：
分配过程：
0
1 81
2 22
3 73 93 43
4 14
5 55 65
6
7
8 28
9 39
接下来将这些桶子中的数值重新串接起来，成为以下的数列：
收集过程：
81, 22, 73, 93, 43, 14, 55, 65, 28, 39
接着再进行一次分配，这次是根据十位数来分配：
分配过程：
0
1 14
2 22 28
3 39
4 43
5 55
6 65
7 73
8 81
9 93
接下来将这些桶子中的数值重新串接起来，成为以下的数列：
收集过程：
14, 22, 28, 39, 43, 55, 65, 73, 81, 93
这时候整个数列已经排序完毕；如果排序的对象有三位数以上，则持续进行以上的动作直至最高位数为止。
算法的实现：
#include <stdio.h>
#include <stdlib.h>
#define RADIX_10 10 // 整型排序
/********************************************************
*函数名称：print
*参数说明：array 无序数组
* length 数组长度
*说明： 输出数组内容
*********************************************************/
void print(unsigned int array[], int length) {
for (int j = 0; j < length; j++) {
printf(" %d ", array[j]);
}
printf("\n");
}
/********************************************************
*函数名称：getLoopTimes
*参数说明：num 一个整形数据
*说明： 返回num的位数
*********************************************************/
int getLoopTimes(unsigned int num) {
int count = 1;
unsigned int temp = num / 10;
while (temp != 0) {
count ++;
temp = temp / 10;
}
return count;
}
/********************************************************
*函数名称：getMaxNum
*参数说明：array 代排序的数
* length 数组长度
*说明： 返回最大值
*********************************************************/
unsigned int getMaxNum(unsigned int array[], int length) {
unsigned int max = 0;
for (int i = 0; i < length; i++) {
if (max < array[i]) {
max = array[i];
}
}
return max;
}
/********************************************************
*函数名称：getNumInPos
*参数说明：num 一个整形数据
* pos 表示要获得的整形的第pos位数据
*说明： 找到num的从低到高的第pos位的数据
*********************************************************/
int getNumInPos(int num, int pos) {
// 求桶的 index 的除数，如：798
// 个位桶 index = (798 / 1) % 10 = 8
// 十位桶 index = (798 / 10) % 10 = 9
// 百位桶 index = (798 / 100) % 10 = 7
int temp = 1;
for (int i = 0; i < pos - 1; i++) {
temp *= 10;
}
return (num / temp) % 10;
}
/********************************************************
*函数名称：radixSort
*参数说明：array 无序数组
* length 数组长度
*说明： 基数排序
*********************************************************/
void radixSort(unsigned int array[], int length) {
// 分别为 0~9 的序列空间
unsigned int *radixArrays[RADIX_10];
for (int i = 0; i < RADIX_10; i ++) {
radixArrays[i] = (unsigned int *)malloc(sizeof(unsigned int) * (length + 1));
radixArrays[i][0] = 0; // 下标为0处元素记录这组数据的个数
}
// 获取数组中的最大数
unsigned int maxNum = getMaxNum(array, length);
// 获取最大数的位数，也是再分配的次数
int loopTimes = getLoopTimes(maxNum);
// 对每一位进行分配
for (int pos = 1; pos <= loopTimes; pos ++) {
// 分配过程
for (int i = 0; i < length; i ++) {
int num = getNumInPos(array[i], pos);
int index = ++ radixArrays[num][0];
radixArrays[num][index] = array[i];
}
// 收集过程
for (int i = 0, j = 0; i < RADIX_10; i ++) {
for (int k = 1; k <= radixArrays[i][0]; k ++) {
array[j++] = radixArrays[i][k];
}
radixArrays[i][0] = 0; // 复位
}
// 输出数组内容
print(array, length);
}
}
int main(int argc, const char * argv[]) {
unsigned int radixArray[10] = { 73, 22, 93, 43, 55, 14, 28, 65, 39, 81 };
radixSort(radixArray, 10);
print(radixArray, 10);
return 0;
}
通过测试，发现程序不对负数进行排序，下面我们实现对负数排序的代码：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define NULLNUM -1111
// 输出数组内容
void print(int array[], int length) {
for (int j = 0; j < length; j++) {
printf(" %d ", array[j]);
}
printf("\n");
}
// a.计算在某一分位上的数据
int pre_process_data(int array[], int length, int weight) {
int index;
int value = 1;
for(index = 0; index < weight-1; index++) {
value *= 10;
}
for(index = 0; index < length; index ++) {
array[index] = (array[index] / value) % 10;
}
for(index = 0; index < length; index ++) {
if(0 != array[index]) {
return 1;
}
}
return 0;
}
// b.对某一分位上的数据按照[-9~9]排序
void sort_for_basic_number(int array[], int length, int swap[]) {
int index;
int basic;
int total = 0;
for(basic = -9; basic < 10; basic++) {
for(index = 0; index < length; index++) {
if(NULLNUM != array[index] && basic == array[index]) {
swap[total ++] = array[index];
array[index] = NULLNUM;
}
}
}
memmove(array, swap, sizeof(int) * length);
}
// c.根据b中的排序结果，对实际的数据进行排序
void sort_data_by_basic_number(int array[], int data[], int swap[], int length, int weight) {
int index;
int outer;
int inner;
int value = 1;
for(index = 0; index < weight-1; index++) {
value *= 10;
}
for(outer = 0; outer < length; outer++) {
for(inner = 0; inner < length; inner++) {
if(NULLNUM != array[inner] && data[outer]==((array[inner] / value) % 10)) {
swap[outer] = array[inner];
array[inner] = NULLNUM;
break;
}
}
}
memmove(array, swap, sizeof(int) * length);
return;
}
// 把a、b、c组合起来构成基数排序，直到某一分位上的数据为0
void radix_sort(int array[], int length) {
int count;
int weight = 1;
int* pData;
int* swap;
if(NULL == array || 0 == length)
return;
pData = (int*)malloc(sizeof(int) * length);
if (NULL == pData) {
printf("malloc error");
return;
}
memmove(pData, array, length * sizeof(int));
swap = (int*)malloc(sizeof(int) * length);
if (NULL == swap) {
printf("malloc error");
return;
}
while(1){
count = pre_process_data(pData, length, weight);
if(!count) {
break;
}
sort_for_basic_number(pData, length, swap);
sort_data_by_basic_number(array, pData, swap, length, weight);
memmove(pData, array, length * sizeof(int));
weight ++;
}
free(pData);
free(swap);
return;
}
int main(int argc, const char * argv[]) {
int array[8] = { 49, 38, 65, -7, -110, 10, -20, -49 };
radix_sort(array, 8);
print(array,8);
return 0;
}
总结
时间复杂度：
通过上文可知，假设在基数排序中，r为基数，d为位数。则基数排序的时间复杂度为O(d(n+r))。我们可以看出，基数排序的效率和初始序列是否有序没有关联。
空间复杂度：
在基数排序过程中，对于任何位数上的基数进行“装桶”操作时，都需要n+r个临时空间。
算法稳定性：
在基数排序过程中，每次都是将当前位数上相同数值的元素统一“装桶”，并不需要交换位置。所以基数排序是稳定的算法。
