小撒是一只好學(xué)的小鴨子煮岁，這天农尖，小撒在學(xué)習(xí)算法
基數(shù)排序（Radix Sort）
如前所述，計(jì)數(shù)排序帶來了空間成本太大的問題剧浸。為了解決這一問題锹引，我們將在其基礎(chǔ)上演變出新的算法：基數(shù)排序。
為了使得計(jì)數(shù)數(shù)組只開辟固定有限的空間唆香，我們可以按位對(duì)元素進(jìn)行排序嫌变。為了方便，我們以十進(jìn)制為例躬它，排序數(shù)組[329,657,457,839,436,720,355]：
基數(shù)排序示例
正確的做法是從低位開始向高位對(duì)元素進(jìn)行排序腾啥，排序先使用元素的個(gè)位，然后是十位冯吓、百位...
而計(jì)數(shù)排序穩(wěn)定排序的特性是這種算法得以正確運(yùn)行的關(guān)鍵之一倘待，使得基數(shù)排序在高位排序過程中保持了低位順序的正確性，例如在個(gè)位排序時(shí)15在19之前组贺，那么在十位排序時(shí)兩者十位都是1的情況下兩者將保持個(gè)位的順序凸舵。
當(dāng)然對(duì)于計(jì)算機(jī)體系而言，以2為底的冪次作為基數(shù)將使得排序更快失尖，因?yàn)槲覀兛梢杂酶咝У奈徊僮鱽慝@取每一位的值啊奄。我們以8進(jìn)制為：
獲得十進(jìn)制數(shù)113的8進(jìn)制表示的第2位
代碼示例（js）
const countingSort = (arr, i) => {
const counters = Array(10).fill(0)
arr.forEach((item) => {
counters[item[i]]++
})
counters.forEach((item, index) => {
if (index !== 0) {
counters[index] += counters[index - 1]
}
})
const rtn = Array(arr.length)
for (let j = arr.length - 1; j >= 0; j--) {
const item = arr[j]
const pos = counters[item[i]] - 1
rtn[pos] = item
counters[item[i]] = pos
}
return rtn
}
const sort = (arr) => {
const max = getMax(arr)
const digits = Math.floor(Math.log10(max)) + 1
let map = arr.map((x) => {
const v = Array(digits).fill(0).map((_, i) => {
return Math.floor(x / Math.pow(10, i)) % 10
})
v.push(x)
return v
})
let i = 0
while (i < digits) {
map = countingSort(map, i)
i++
}
return map.map(item => item[digits])
}
小結(jié)
基數(shù)排序在計(jì)數(shù)排序的基礎(chǔ)上，延續(xù)了線性時(shí)間的時(shí)間成本雹仿，同時(shí)將空間成本化為常量增热，是一種優(yōu)秀的排序算法。
