基数排序

思想

基数排序（Radix sort）要求待排序列可以分割出独立的位来比较，而且位之间有递进的关系，如果 a 数据的高位比 b 数据大，那剩下的低位就不用比较了。除此之外，每一位的数据范围不能太大，要可以用线性排序算法来排序，否则，基数排序的时间复杂度就无法达到 O(n) 。

可能看完基数排序的算法思想不好理解，我们可以结合一个例子来理解。例如要比较两个手机号码 a，b 的大小，如果在前面几位中，a 手机号码已经比 b 手机号码大了，那后面的几位就不用再比较了，并且手机号都是 0-9 的数字，因此比较适合基数排序。

为了更好的理解排序的过程，我们可以简化一下场景为字符串长度为 3 的比较进行排序，排序过程如下图所示：

tip

在按照位来排序时，要求排序算法必须是稳定的。假设如果排序算法不稳定，可能存在低位比较时相同，但是因为算法不稳定而交换了位置，然后后面高位出现不同时，之前交换位置的数据，现在又重新交换了回来。

当待排序列位数长短不同时，可以采用末尾补齐的办法，例如对字典中所有的英文字典排序，就可以通过再末尾补 0 的办法，让所有数据的位数都和最长的单词相同，此时便可以通过基数排序来排序了。

实现

// TODO

分析

时间复杂度

当每一位进行比较的时候，可以采用线性的桶排序，时间复杂度 O(n)，位数为 K，所以时间复杂度为 O(k*n)，因为位数 k 较小，所以基数排序的时间复杂度可以做到 O(n)。