Python桶排序算法

由于桶排序算法把每个数都放到合适的“桶”里进行排序,因此而得名。桶排序的算法原理可以理解为创建一个新的数组,把数依次放入合适的桶内,再按一定顺序输出桶。

当每个桶的数据范围为 1 且数据皆为整数时,桶排序的时间复杂度在所有情况下都是 O(n),因为它是一个线性的排序算法。但是,它的空间需求要视排序数据的范围而定,所以极有可能浪费很多空间。

假设我们有 10 个整数 [1,1,3,19,35,49,50,5,10,16],它们的范围在 1~50。如图 1 所示,我们建立 50 个存放数据的桶。
建立空桶
图 1:建立空桶

如图 2 所示,把数据放入对应编号的桶中。然后,直接把装有元素的桶的编号输出,输出的次数以桶内元素的数量为准。
把数据放入桶中
图 2:把数据放入桶中
用代码实现上述的桶排序非常简单。

桶排序代码(固定元素范围版):
countn = [0]*51 #建立足够的桶
nums,result = [1,1,3,19,35,49,50,5,10,16],[]
for i in nums:
    countn[i] += 1 #统计每个元素出现的次数
for i in range(1,len(countn)):
    if countn[i]: #如果桶内有元素
        result += [i]*countn[i] #往结果数组中加上相应数量的元素
print(result)
运行程序,输出结果为:

[1, 1, 3, 5, 10, 16, 19, 35, 49, 50]

代码中,countn[i] 存储的值是元素 i 在数组中出现的次数。所以,在往 result 数组中添加元素时,要添加 countn[i] 次。代码实现的程序是升序排序,若想要降序排序,遍历 countn 数组时从后往前即可。

如果要排序的元素范围不确定,我们需要采用稍有不同的一种方法。

桶排序代码(非固定元素范围版):
nums,result = [19,21,23,14,35,49,37,59,10,16],[]
minv,maxv = min(nums),max(nums) #找出所有元素中的最小值和最大值
countn = [0]*(maxv-minv+1) #算出需要桶的最大个数
for i in nums:
    countn[i-minv] += 1 #桶的编号与对应元素不一致,需要通过计算调整
for i in range(1,len(countn)):
    if countn[i]:
        result += [i+minv]*countn[i]
print(result)
运行程序,输出结果为:

[14, 16, 19, 21, 23, 35, 37, 49, 59]

在这段代码中,与固定元素范围版不一样的地方在于每个桶的编号和它存储的元素不同。最小值对应的是编号 0,最小值+1 对应的是编号 1,也就是说,元素i对应的编号是它自身减去最小值。往桶里放入元素和输出元素时都要以这个规律为准。

以上的方法都只适用于对整数的排序。可以看出,为了排序定义的大部分桶都没有被使用。如果数据量不大但出现了极值,会造成严重的空间浪费。为了满足这两种需求,我们可以把排序范围分段,例如在 1<x≤100 范围内的元素放入同一个桶内,100<x≤200 的元素放入一个桶内,以此类推。每一个桶内所包含的元素范围大小必须相等。在每一个桶内,再使用其他排序算法对元素进行排序,之后按顺序合并所有的桶即可。