一步一步写算法（之基数排序）
【 声明：版权所有，欢迎转载，请勿用于商业用途。 联系信箱：feixiaoxing @163.com】
基数排序是另外一种比较有特色的排序方式，它是怎么排序的呢？我们可以按照下面的一组数字做出说明：12、 104、 13、 7、 9
（1）按个位数排序是12、13、104、7、9
（2）再根据十位排序104、7、9、12、13
（3）再根据百位排序7、9、12、13、104
这里注意，如果在某一位的数字相同，那么排序结果要根据上一轮的数组确定，举个例子来说：07和09在十分位都是0，但是上一轮排序的时候09是排在07后面的；同样举一个例子，12和13在十分位都是1，但是由于上一轮12是排在13前面，所以在十分位排序的时候，12也要排在13前面。
所以，一般来说，10基数排序的算法应该是这样的？
（1）判断数据在各位的大小，排列数据；
（2）根据1的结果，判断数据在十分位的大小，排列数据。如果数据在这个位置的余数相同，那么数据之间的顺序根据上一轮的排列顺序确定；
（3）依次类推，继续判断数据在百分位、千分位......上面的数据重新排序，直到所有的数据在某一分位上数据都为0。
说了这么多，写上我们的代码。也希望大家自己可以试一试。
a）计算在某一分位上的数据
int pre_process_data(int array[], int length, int weight) { int index ;
int value = https://www.it610.com/article/1;
for(index = 0;
index < weight;
index++) value *= 10;
for(index = 0;
index < length;
index ++) array[index] = array[index] % value /(value /10);
for(index = 0;
index < length;
index ++) if(0 != array[index]) return 1;
return 0;
}
b）对某一分位上的数据按照0~10排序
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(-10 != array[index] && basic == array[index] ){ swap[total ++] = array[index];
array[index] = -10;
} } } 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 = https://www.it610.com/article/1;
for(index = 0;
index < weight;
index++) value *= 10;
for(outer = 0;
outer < length;
outer++){ for(inner = 0;
inner < length;
inner++){ if(-10 != array[inner] && data[outer]==(array[inner] % value /(value/10))){ swap[outer] = array[inner];
array[inner] = -10;
break;
} } } memmove(array, swap, sizeof(int) * length);
return;
}
d）把a、b、c组合起来构成基数排序，直到某一分位上的数据为0
void radix_sort(int array[], int length) { int* pData;
int weight = 1;
int count;
int* swap;
if(NULL == array || 0 == length) return;
pData = https://www.it610.com/article/(int*)malloc(sizeof(int) * length);
assert(NULL != pData);
memmove(pData, array, length * sizeof(int));
swap = (int*)malloc(sizeof(int) * length);
assert(NULL != swap);
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;
}
总结：
（1）测试的时候注意负数的情形
（2）如果在某一位数据相同，那么需要考虑上一轮数据排序的情况
【一步一步写算法（之基数排序）】 （3）代码中多次分配小空间，此处代码待优化
补充：
（1） 10月15日晚上修改了余数取值范围，这样负数也可以参加排序
（2）10月16日上午增加了一个swap内存分配，避免了内存的重复分配和释放
（3）10月16日上午删除了count计数，一旦发现有不等于0的数据直接返回为1，不需要全部遍历数据
推荐阅读
- JAVA（抽象类与接口的区别&重载与重写&内存泄漏）
- 今天写一些什么
- 小影写在2018九月开学季
- 画解算法（1.|画解算法：1. 两数之和）
- 标签、语法规范、内联框架、超链接、CSS的编写位置、CSS语法、开发工具、块和内联、常用选择器、后代元素选择器、伪类、伪元素。
- Guava|Guava RateLimiter与限流算法
- 写给陈羡
- angular2内置管道
- 也许第一步很难，但跨过去就好了
- 尖子生的启示（３）