桶排序：（Bucket sort）或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶里。每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序），最后依次把各个桶中的记录列出来记得到有序序列。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间（Θ(n)）。但桶排序并不是比较排序，他不受到O(n log n)下限的影响。

def bucket_sort(li, n=100, max_num=1000):
    """
    桶排序 时间复杂度 O(n+k) 最坏情况 O(n²+k) 空间复杂度 O(nk)
    :param li:
    :param n:
    :param max_num:
    :return:
    """
    buckets = [[] for _ in range(n)]  # 创建桶
    for v in li:
        i = min(v // (max_num // n), n - 1)  # i 表示 v 放到几号桶
        buckets[i].append(v)  # 把 v 加到桶里
        # 保持桶内的顺序
        for j in range(len(buckets[i]) - 1, 0, -1):
            if buckets[i][j] < buckets[i][j - 1]:
                buckets[i][j], buckets[i][j - 1] = buckets[i][j - 1], buckets[i][j]
            else:
                break
    sorted_li = []
    for buc in buckets:
        sorted_li.extend(buc)
    return sorted_li


import random

li = [random.randint(1, 1000) for _ in range(100)]
print(li)
li = bucket_sort(li)
print(li)