跳到主要内容

简介

基数排序是一种非比较排序算法,时间复杂度是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 组成的二进制数值。那这样的话,岂不是任意一个非负整数序列都可以用基数排序算法?理论上是的,假设待排序序列中最大整数为26412^64-1,则最大位数d=64,时间复杂度为O(64n)。可见任意一个非负整数序列都可以在线性时间内完成排序。

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

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