排序算法（十二）基数排序
基数排序（radix sort）是桶排序改进版，该算法是通过按位收集的思想，即将一个整数，按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。
图片演示
基数排序图-1
基数排序图-2
在上图中，从最低位开始，依次进行排序。
按照个位数进行排序。
按照十位数进行排序。
按照百位数进行排序。
排序后，数列就变成了一个有序序列。
代码实现（TypeScript实现）
/**
* 基数排序
* @param arr 源数组
*/
function radixSort(arr: Array<number>): Array<number> {
if (!arr) { return arr }
// 找最大数
let max = arr[0];
arr.forEach(element => {
if (element > max) { max = element }
});
// 开始排序（最外层循环是指最大数的位数数）
let buckets: Array<Array<number>> = new Array<Array<number>>();
for (let i = 0, len = max.toString().length, mod = 10, dev = 1; i < len; i++, mod *= 10, dev *= 10) {
// 按 “个 -> 百 -> 千”位数顺序排序
for (let j = 0, len = arr.length; j < len; j++) {
let index = ((arr[j] % mod) / dev) | 0;
if (!buckets[index]) { buckets[index] = new Array<number>() };
buckets[index].push(arr[j]);
}
// 重新复制到源数组里
for (let k = 0, len = buckets.length, pos = 0; k < len; k++) {
let value = null;
if (buckets[k]) {
while (value = buckets[k].shift()) {
arr[pos++] = value
}
}
}
}
return arr;
}
let originData: Array<number> = [5, 6, 7, 9, 10, 15, 13, 19, 5, 9, 13, 10];
console.log(radixSort(originData));
分析
基数排序基于分别排序，分别收集，所以是稳定的。但基数排序的性能比桶排序要略差，每一次关键字的桶分配都需要O(n)的时间复杂度，而且分配之后得到新的关键字序列又需要O(n)的时间复杂度。假如待排数据可以分为d个关键字，则基数排序的时间复杂度将是O(d*2n) ，当然d要远远小于n，因此基本上还是线性级别的。
基数排序的空间复杂度为O(n+k)，其中k为桶的数量。一般来说n>>k，因此额外空间需要大概n个左右。
