sorting/radix-sort/README

简介

基数排序是一种非比较排序算法，时间复杂度是O(n)。它的主要思路是，

1. 将所有待排序整数（注意，必须是非负整数）统一为位数相同的整数，位数较少的前面补零。一般用 10 进制，也可以用 16 进制甚至 2 进制。所以前提是能够找到最大值，得到最长的位数，设k进制下最长为位数为d。
2. 从最低位开始，依次进行一次稳定排序。这样从最低位一直到最高位排序完成以后，整个序列就变成了一个有序序列。

举个例子，有一个整数序列，0, 123, 45, 386, 106，下面是排序过程：

• 第一次排序，个位，000 123 045 386 106，无任何变化
• 第二次排序，十位，000 106 123 045 386
• 第三次排序，百位，000 045 106 123 386

最终结果，0, 45, 106, 123, 386, 排序完成。

为什么同一数位的排序子程序要用稳定排序？因为稳定排序能将上一次排序的成果保留下来。例如十位数的排序过程能保留个位数的排序成果，百位数的排序过程能保留十位数的排序成果。

能不能用 2 进制？能，可以把待排序序列中的每个整数都看成是 01 组成的二进制数值。那这样的话，岂不是任意一个非负整数序列都可以用基数排序算法？理论上是的，假设待排序序列中最大整数为$$2^64-1$$，则最大位数d=64，时间复杂度为O(64n)。可见任意一个非负整数序列都可以在线性时间内完成排序。

既然任意一个非负整数序列都可以在线性时间内完成排序，那么基于比较排序的算法有什么意义呢？基于比较的排序算法，时间复杂度是O(nlogn)，看起来比O(64n)慢，仔细一想，其实不是，O(nlogn)只有当序列非常长，达到$$2^{64}$$个元素的时候，才会与O(64n)相等，因此，64 这个常数系数太大了，大部分时候，n远远小于$$2^{64}$$，基于比较的排序算法还是比O(64n)快的。

当使用 2 进制时，k=2最小，位数d最大，时间复杂度O(nd)会变大，空间复杂度O(n+k)会变小。当用最大值作为基数时，k=maxV最大，d=1最小，此时时间复杂度O(nd)变小，但是空间复杂度O(n+k)会急剧增大，此时基数排序退化成了计数排序。