介绍

桶排序是一个排序算法，工作的原理是将数组中的元素分到有限数量的桶里。每个桶再个别排序（有可能再使用别的排序算法，或是以递归方式继续使用桶排序进行排序）。

复杂度：

最坏时间复杂度：O(n^2)
平均时间复杂度：O(n + k)
最坏空间复杂度：O(n * k)

步骤

桶排序以下列程序进行：

• 设置一个定量的数组当作空桶子。
• 寻访序列，并且把项目一个一个放到对应的桶子去。
• 对每个不是空的桶子进行排序。
• 从不是空的桶子里把项目再放回原来的序列中。

python

def indexFor(a, min, step):
    return (a - min) // step

def bucket_sort(lst):
    # 查找lst中的最小值和最大值
    max, min = lst[0], lst[0]
    for i in lst:
        if i > max:
            max = i
        if i < min:
            min = i
    # 定义一个桶数
    bucketNum = max // 2 - min // 2 + 1
    # 创建bucketNum个空桶
    buckList = []
    for i in range(bucketNum):
        buckList.append([])
    # 根据定义把lst中的元素放进不同的桶中, 前一个桶中的所有元素都小于后一个桶中的所有元素
    for i in lst:
        index = indexFor(i, min, 2)
        buckList[index].append(i)
    index = 0
    for bucket in buckList:
        bucket = insert_sort(bucket)
        for j in bucket:
            lst[index] = j
            index += 1
    return lst

# 桶内的元素进行插入排序
def insert_sort(bucket):
    if len(bucket) <= 1:
        return bucket
    else:
        for i in range(1, len(bucket)):
            key = bucket[i]
            j = i - 1
            while j >= 0:
                if bucket[j] > key:
                    bucket[j + 1] = bucket[j]
                    bucket[j] = key
                j -= 1
        return bucket

lst = [3, 5 ,2, 6, 8, 1, 9, 7]
print(bucket_sort(lst))