排序算法（十二）基數(shù)排序
??基數(shù)排序（radix sort）是桶排序改進(jìn)版叔汁，該算法是通過按位收集的思想，即將一個整數(shù)检碗，按照低位先排序据块，然后收集；再按照高位排序折剃，然后再收集另假；依次類推，直到最高位怕犁。有時候有些屬性是有優(yōu)先級順序的边篮，先按低優(yōu)先級排序，再按高優(yōu)先級排序奏甫。最后的次序就是高優(yōu)先級高的在前戈轿，高優(yōu)先級相同的低優(yōu)先級高的在前。
圖片演示
基數(shù)排序圖-1
基數(shù)排序圖-2
在上圖中阵子，從最低位開始思杯，依次進(jìn)行排序。
按照個位數(shù)進(jìn)行排序挠进。
按照十位數(shù)進(jìn)行排序色乾。
按照百位數(shù)進(jìn)行排序。
排序后领突，數(shù)列就變成了一個有序序列杈湾。
代碼實(shí)現(xiàn)（TypeScript實(shí)現(xiàn)）
/**
* 基數(shù)排序
* @param arr 源數(shù)組
*/
function radixSort(arr: Array<number>): Array<number> {
if (!arr) { return arr }
// 找最大數(shù)
let max = arr[0];
arr.forEach(element => {
if (element > max) { max = element }
});
// 開始排序（最外層循環(huán)是指最大數(shù)的位數(shù)數(shù)）
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) {
// 按 “個 -> 百 -> 千”位數(shù)順序排序
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]);
}
// 重新復(fù)制到源數(shù)組里
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));
分析
基數(shù)排序基于分別排序，分別收集攘须，所以是穩(wěn)定的漆撞。但基數(shù)排序的性能比桶排序要略差，每一次關(guān)鍵字的桶分配都需要O(n)的時間復(fù)雜度于宙，而且分配之后得到新的關(guān)鍵字序列又需要O(n)的時間復(fù)雜度浮驳。假如待排數(shù)據(jù)可以分為d個關(guān)鍵字，則基數(shù)排序的時間復(fù)雜度將是O(d*2n) 捞魁，當(dāng)然d要遠(yuǎn)遠(yuǎn)小于n至会，因此基本上還是線性級別的。
基數(shù)排序的空間復(fù)雜度為O(n+k)谱俭，其中k為桶的數(shù)量奉件。一般來說n>>k宵蛀，因此額外空間需要大概n個左右。
