Python实现桶排序与基数排序详解及性能分析

本文首先通过具体案例阐述两种排序算法的操作流程，随后展示Python代码实现，最后对桶排序的性能优劣进行简要总结。

一、桶排序：

以数组[5,3,6,1,2,7,5,10]为例进行排序演示。

由于数组元素值均位于1至10之间，因此建立10个桶。

[0 0 0 0 0 0 0 0 0 0] 桶

[1 2 3 4 5 6 7 8 9 10] 桶所代表的数值

遍历数组，首个数字为5，对应第五个桶计数加1。

[0 0 0 0 1 0 0 0 0 0]

第二个数字为3，对应第三个桶计数加1。

[0 0 1 0 1 0 0 0 0 0]

遍历完成后状态

[1 1 1 0 2 1 1 0 0 1]

输出结果

[1 2 3 5 5 6 7 10]

代码实现：

def bucket_sort(lst):
 buckets = [0] * ((max(lst) - min(lst))+1)
 for i in range(len(lst)):
  buckets[lst[i]-min(lst)] += 1
 res=[]
 for i in range(len(buckets)):
  if buckets[i] != 0:
   res += [i+min(lst)]*buckets[i]
 return res

二、基数排序：

例如，对如下数据序列进行排序。

192,221,12,23

观察可知，每个数据最多包含3位数字，因此可将每个数据拆分为3个关键字：百位（高位）、十位、个位（低位）。若按常规思维，应先比较百位，百位大的数值大；百位相同时比较十位，十位大的数值大；最后比较个位。基数排序对任一子关键字排序时，必须借助另一种排序方法，且该方法必须是稳定的。对于多关键字拆分出的子关键字，其值必然位于0-9的可枚举范围内，范围较小，因此使用桶式排序效率极高。

代码：

from random import randint
def radix_sort(lis,d):
 for i in xrange(d):#d轮排序
  s = [[] for k in xrange(10)]#因为每一位数字都是0~9，故建立10个桶
  for j in lis:
   s[j/(10**i)%10].append(i)
  li = [a for b in s for a in b]
 return li

对数组元素按从低位到高位的顺序进行排序。对于[192,221,12,23]，第一轮按个位数字分组，结果为s[1]=[221], s[2]=[192,12], s[3]=23；第二轮按十位数字排序，结果为s[1]=[12], s[2]=[221,23], s[9]=[192]；第三轮按百位数字排序，结果为s[0]=[12,23], s[1]=[192], s[2]=[221]。

总结：

桶排序与基数排序常归为桶式排序范畴，其中基数排序实质上是进行了多轮桶排序。桶式排序不属于基于比较的排序方法，而是一种巧妙的排序策略，但其应用需满足两个特征：待排序列的值必须处于一个可枚举的范围内；且该可枚举范围不宜过大，否则排序开销将显著增加。该算法适用于学生成绩排序等场景，因为若干学生的成绩范围通常仅在100以内。

桶式排序的空间开销较大，它需要两个数组：第1个buckets数组用于记录“落入”各桶中元素的个数，进而确定各元素在有序序列中的位置；第2个数组用于缓存待排数据。该算法仅能处理整型数组。此外，当k较大而数组长度n较小（即k>>n）时，辅助数组C[k+1]的空间消耗较大。

以上这篇基于Python的桶排序与基数排序总结即为大家分享的全部内容，希望能提供参考，也希望大家多多支持本站。