算法精粹(algorithm-essentials)

感谢soulmachine@github提供内容
**基数排序**是一种非比较排序算法,时间复杂度是`O(n)`。它的主要思路是,

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

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

* 第一次排序,个位,00**0** 12**3** 04**5** 38**6** 10**6**,无任何变化
* 第二次排序,十位,0**0**0 1**0**6 1**2**3 0**4**5 3**8**6
* 第三次排序,百位,**0**00 **0**45 **1**06 **1**23 **3**86

最终结果,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)`会急剧增大,此时**基数排序退化成了计数排序**。