桶排序

工作原理

将数组分到有限数量的桶里，每个桶子里再个别排序。当要排序的数组内的数值是均匀分配的时候，桶排序使用线性时间 Θ(n)。
桶排序是稳定的。
桶排序主要用于有大量重复数据和明确知道数据边界的情况下，进行排序。

def bucket_sort(nums):
    # 选择一个最大的数
    max_num = max(nums)
    # 创建一个元素全是0的列表, 当做桶
    bucket = [0]*(max_num+1)
    # 把所有元素放入桶中, 即把对应元素个数加一
    for i in nums:
        bucket[i] += 1

    # 存储排序好的元素
    sort_nums = []
    # 取出桶中的元素
    for j in range(len(bucket)):
        if bucket[j] != 0:
            for y in range(bucket[j]):
                sort_nums.append(j)
    return sort_nums