十大排序算法（九）--- 基数排序
对于基于比较操作的排序算法(比如：归并排序，堆排序以及快速排序等等)，它们的时间复杂度是O(nlogn)，无法继续减少时间复杂度。虽然于计数排序则是线性时间复杂度，(如：当元素的值分布在1到k时，计数排序的时间复杂度为O(n+k)), 但如果元素的值分布为1到n^2呢？那么计数排序的复杂度变为O(n^2) ，这个比基于比较操作的排序算法更糟。在这种情况下，还有办法获得线性时间复杂度吗？答案是：基数排序。
基数排序的思想是对每一个待排序元素从最低位开始到最高位进行逐位排序。在进行逐位排序时可以选择计数排序(或者其它稳定的排序算法)。下图展示了基数排序的思想和过程。
上图对元素的每一位数字使用不同颜色进行了标记，方便阅读。针对位数不整齐的情况，我们采用了高位补0的办法，可以从上图中看到。我们对每一位数字排序时采用了计数排序算法，不了解计数排序的同学可以参考我之前的一篇文章<< 10大排序算法-计数排序>>。
我们来分析一下上面基数排序的时间复杂度。我们假设待排序的数组中最大数字共有d位数字组成。n表示待排序元素个数，b表示基数(比如，十进制：那么b=10)。我们知道，计数排序的时间复杂度为O(n+k),这里k表示待排序元素中最大数字。在基数排序时，我们针对每一位排序时，最大元素值不会>=b，因此对每一位的排序时间复杂度为O(n+b)，一共有d位，所以基数排序的时间复杂度为O(d*(n+b))。这个时间复杂度如何呢？我们假设待排序元素最大值为max, 那么d就可以用O(logb(max)), 所以整个时间复杂度为: O((n+b)* logb(max))。这比基于比较的排序法时间复杂度(O(nlogn))看上去要差。我们如果限制一下max的上限，假设max <= n^c，c是一个常数。那么基数排序的时间复杂度变为:O(nlogb(n))。但是仍然比基于比较的排序法时间复杂度(O(nlogn))看上去要差。
这里我们再进一步考虑b这个因子。我们可以看到b越大logb(n)越小。如果我们设置b=n, 那么基数排序的时间复杂度变为O(n)。到此，我们得出结论，如果待排序数组每个元素都处于1 ~ n^c之间，并且每个数字都是以n为基数的(或者每个数字都是log2n 位的)，那么使用基数排序的时间复杂度为O(n)。
基于上面的分析，基数排序一般用来对每个元素具有多域属性的情况进行排序。比如对时间进行排序。可以用基数排序，先排日期，再排月份，最后排年份。
下面是基数排序的python代码实现：
import copy
#define data array for sorting
A = [9,12,3,6,4,0,7,9,11,2,8,9,0,1,3,1,10,10,23]
def ascending_sorting(data, max_data, base, n):
while int(max_data/base) > 0:
count = [0 for i in range(0, 10)]
tmp = [0 for i in range(0, n)]
for i in range(0, n):
count[int(data[i]/base)%10] += 1
for i in range(1, 10):
count[i] += count[i-1]
for i in range(n-1, -1, -1):
count[int(data[i]/base)%10] -= 1
tmp[count[int(data[i]/base)%10]] = data[i]
base *= 10
data = copy.deepcopy(tmp)
return data
def descending_sorting(data, max_data, base, n):
while int(max_data/base) > 0:
count = [0 for i in range(0, 10)]
tmp = [0 for i in range(0, n)]
for i in range(0, n):
count[int(data[i]/base)%10] += 1
for i in range(8, -1, -1):
count[i] += count[i+1]
for i in range(n-1, -1, -1):
count[int(data[i]/base)%10] -= 1
tmp[count[int(data[i]/base)%10]] = data[i]
base *= 10
data = copy.deepcopy(tmp)
return data
def radix_sorting(data, flag=True):
"""
if flag = True: than ascending order
else : descending order
"""
#get the max data
max_data = max(data)
base = 1
n = len(data)
if flag == True:
return ascending_sorting(data, max_data, base, n)
else:
return descending_sorting(data,max_data, base, n)
def main():
#Ascending order
print(radix_sorting(A))
#Descending order
print(radix_sorting(A, False))
if __name__=='__main__':
main()
将上面的代码保存到一个文本文件，后缀名修改为.py。可以用python解释器执行一下，会输出如下结果：
可以看到，排序正确。