小撒是一只好学的小鸭子，这天，小撒在学习算法
基数排序（Radix Sort）
如前所述，计数排序带来了空间成本太大的问题。为了解决这一问题，我们将在其基础上演变出新的算法：基数排序。
为了使得计数数组只开辟固定有限的空间，我们可以按位对元素进行排序。为了方便，我们以十进制为例，排序数组[329,657,457,839,436,720,355]：
基数排序示例
正确的做法是从低位开始向高位对元素进行排序，排序先使用元素的个位，然后是十位、百位...
而计数排序稳定排序的特性是这种算法得以正确运行的关键之一，使得基数排序在高位排序过程中保持了低位顺序的正确性，例如在个位排序时15在19之前，那么在十位排序时两者十位都是1的情况下两者将保持个位的顺序。
当然对于计算机体系而言，以2为底的幂次作为基数将使得排序更快，因为我们可以用更高效的位操作来获取每一位的值。我们以8进制为：
获得十进制数113的8进制表示的第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])
}
小结
基数排序在计数排序的基础上，延续了线性时间的时间成本，同时将空间成本化为常量，是一种优秀的排序算法。
