对于经典算法，你是否也遇到这样的情形：学时觉得很清楚，可过阵子就忘了？
本系列文章就尝试解决这个问题。
研读那些排序算法，细品它们的名字，其实都很贴切。
比如基数排序，就是按照数字的“位”来排序。
位，是进位的位，比如十进制数的基数是10，就可以按照个十百千万等位来排序。
上图演示了基数排序算法的总体流程。先按个位从小到大排序，然后再按十位、百位排序。只要排序算法是稳定的，那么最后整体就是有序的。为了方便看出数字的每一位具体是多少，这里对位数少的数字进行了左边补0。
可见该算法的核心在于选择的排序算法是稳定的。
排序是稳定的意思说，排序后，其相同元素的相对顺序并不会改变。比如19和18，按个位排，9大于8，因而顺序是18、19。二者十位上的数值相等（都为1），如果此时排十位的算法是不稳定的话，会可能出现19在前，18在后这样的情形，那么之前先按个位排序的意义将不复存在了。
了解了整体原理后，我们来一步步写出它。
首先，如何判断数字最长有多少位？遍历一遍就能解决：
let array = [666, 520, 36, 49, 9, 600, 8, 502, 998, 32]
let maxLength = 0
for (let v of array) {
let length = String(v).length
if (length > maxLength) {
maxLength = length
}
}
console.log(maxLength) // 3
这里我们取巧，通过转化为字符串，来获取每个数字的位数。也可以通过，找到最大数，用它不断除以10来获取位数。
另一个问题是：如何获取数字某位上的数字呢？
比如获取36的百位上的数字，通过转字符串后，补0取第一位：
String(36).padStart(maxLength, '0')[0] // 0
有了上述铺垫后，整体逻辑就有了：
for (i = 0; i < maxLength; i++) {
array = sort(array, i)
console.log(array)
}
对数组排序三次，每一次的输出作为下一次的输入。其中sort方法只要是稳定的排序算法即可。
这里推荐使用桶排序算法，下面我们简单过一遍。
由于个位上的数值范围是从0到9，需要构建10个桶：
let buckets = []
for (let i = 0; i < 10; i++) {
buckets.push([])
}
然后把按个位上的数值把元素分别分到这些桶里：
for (let v of array) {
let pad = String(v).padStart(maxLength, '0')
let num = pad[maxLength -1]
buckets[num].push(v)
}
console.log(buckets)
// [ [ 520, 600 ], [], [ 502, 32 ], [], [], [], [ 666, 36 ], [], [ 8, 998 ], [ 49, 9 ] ]
因为桶的区间大小特殊（为1），因此桶内部不需再排（有点计数排序的意味）。直接按顺序输出每个桶的元素即可：
let result = []
for (let bucket of buckets) {
result.push(...bucket)
}
console.log(result)
// [ 520, 600, 502, 32, 666, 36, 8, 998, 49, 9 ]
sort方法完整代码是：
function sort(array, index) {
let buckets = []
for (let i = 0; i < 10; i++) {
buckets.push([])
}
for (let v of array) {
let pad = String(v).padStart(maxLength, '0')
let num = pad[maxLength - 1 - index]
buckets[num].push(v)
}
let result = []
for (let bucket of buckets) {
result.push(...bucket)
}
return result
}
至此，基数排序原理和实现已经说完了。查看完整代码：codepen。
需要补充的是，基数排序也有从高位开始遍历的。另外，用它也可以轻松实现字典排序。
这里总结一下，基数排序的性能，取决于内部排序算法的选择。如果使用桶排序，时间复杂度为O(k*n)，其中k为最大元素的位数，一般都是很小数。
基数排序，要做到能分分钟手写出来，是需要掌握其排序原理的。核心是使用稳定排序从低位逐次排列到高位，一旦理解就容易写出来，不需要死记硬背的。
希望有所帮助，本文完。
本系列已经发表文章：
