基数排序（Radix Sort）
一句话总结
基数排序是 计数排序 算法的扩展，它的主要思路是对待排序元素的每一位依次进行计数排序。由于计数排序是稳定的，所以对每一位完成计数排序后，所有元素就完成了排序。
下面这个可视化面板展示了基数排序的过程：点击 let maxLen = 0 这一行代码，可以看到算法将数组元素都转化为了非负数；多次点击 countSort(nums, k) 这一行代码，对每一位执行计数排序；最后点击 nums[i] -= offset 这一行代码，将数组元素转化回原来的值，完成排序：
首先解释一下基数排序（Radix Sort）这个名词。
基数（Radix）其实就是进制的意思，比如十进制数的基数就是 10，二进制数的基数就是 2。看这个名字就知道这个排序算法肯定和数字的进制有关，进而可以推断，这个算法不是通用排序算法，待排序数据必须是整数，或者能够通过某种规则转化成整数，才能使用基数排序。
我发现网上的很多资料会把基数排序和桶排序放在一起，认为基数排序是桶排序的应用。
但我不认同这种看法，我认为基数排序是计数排序的扩展，可以用来解决计数排序空间复杂度过高的问题，和桶排序关系不大。
现在你已经学习过 计数排序 和 桶排序 了，在我介绍了基数排序的原理后，你也可以自己思考一下，它是到底是计数排序的扩展还是桶排序的扩展。
基数排序的原理
基数排序的原理很简单，比方说输入的数组都是三位数 nums = [329, 457, 839, 439, 720, 355, 350]，我们先按照个位数排序，然后按照十位数排序，然后按照百位数排序，最终就完成了整个数组的排序。
这里面的关键在于，对每一位的排序都必须是稳定排序，否则最终结果就不对了。
用这个 nums 数组为例，演示一下基数排序的过程，我把每个数字竖着写，方便查看每一位的排序效果。
首先是初始状态：
329
457
839
439
720
355
350按照个位数进行稳定排序，得到：
720
350
355
457
329
839
439
^再按照十位数进行稳定排序，得到：
720
329
839
439
350
355
457
^最后按照百位数进行稳定排序，得到：
329
350
355
439
457
720
839
^上面就是基数排序的过程，在给出解法代码之前，先解答一些关于基数排序的问题：
1、为什么对每一位必须使用稳定排序？
2、使用什么稳定排序比较好，为什么？
3、如果待排序数组中的数字不全是三位数，怎么办？有负数怎么办？
4、必须按照从个位数到高位数的顺序进行排序吗？是否可以反过来，从高位数到个位数进行排序？
为什么对每一位必须使用稳定排序
举个很简单的例子：
56
57个位数已经排好序了，现在要对十位数排序。
十位数都是 5，稳定排序可以保证这两个 5 的顺序不变，最终的结果就是正确的；而如果使用不稳定排序，这两个 5 的顺序就可能被打乱，最终的结果就不对了。