1. 桶排序

桶排序：把元素分组，放在各个桶里，再对每个桶内的元素进行排序，最后将桶内的数据合并即可。

时间复杂度：
    最坏情况：O(n^2 + k)
    平均情况：O(n + k)
空间复杂度：O(nk)
复制

2. 代码1

def bucket_sort(li, n=10, max_num=100):
    '''
    :param li:待排序列表
    :param n: 桶的数量
    :param max_num:列表中数的最大范围
    :return: 排过序的列表
    '''
    # 1. 创建桶（注意：一个桶就是一个列表）
    buckets = [[] for i in range(n)]
    # 2. 将数据分桶 并在桶内并排序
    for var in li:  # 遍历列表中所有的数
        i = min(var // (max_num // n), n - 1)  # i 表示 var 放到几号桶里
        # max_num // n 代表一个桶放多少个数(每个桶有几个数)
        # var // (max_num // n)  要放在第几个桶里
        # 用min是为了防止比如100这个数出现，正常来说应该放到第10个桶，但我们只有0-9号桶，所以取较小值，让100放进9号桶
        buckets[i].append(var)  # 将数添加到桶里边
        # 桶内排序
        for j in range(len(buckets[i]) - 1, 0, -1):  # [1, 1, 1, 2, 5, 3] 拿3和它前面的数比较
            if buckets[i][j] < buckets[i][j - 1]:  # 如果后面的数比前面的数小，交换
                buckets[i][j], buckets[i][j - 1] = buckets[i][j - 1], buckets[i][j]
            else:  # 如果后面的数大于前面的数就跳出
                break
    # print(buckets)
    # 4. 将二维列表拆分为单个元素
    sorted_li = []
    for buc in buckets:
        sorted_li.extend(buc)  # extend:追加列表，列表被拆分为一个一个元素
    return sorted_li


import random

li = [random.randint(0, 100) for i in range(100)]
print(li)
li = bucket_sort(li)
print(li)
复制

2. 代码2

def bucket_sort(li, n=10, max_num=100):
    # 1. 创建桶
    buckets = [[] for _ in range(n)]
    # 2. 将数据分桶
    for item in li:
        pos = min(item // (max_num // n), n - 1)
        buckets[pos].append(item)
    # 3. 并在桶内并排序
    for index, val in enumerate(buckets):
        buckets[index] = sorted(val)
    print(buckets)
    # 4. 将二维列表拆分为单个元素,并添加到列表中
    li.clear()
    for i in buckets:
        li.extend(i)


li = [28, 73, 41, 76, 31, 69, 25, 58, 27, 93, 3, 55, 78, 70, 35, 49, 44, 58, 18, 81]
print(li)
bucket_sort(li)
print(li)
复制

运行结果如下：

[28, 73, 41, 76, 31, 69, 25, 58, 27, 93, 3, 55, 78, 70, 35, 49, 44, 58, 18, 81]
[[3], [18], [25, 27, 28], [31, 35], [41, 44, 49], [55, 58, 58], [69], [70, 73, 76, 78], [81], [93]]
[3, 18, 25, 27, 28, 31, 35, 41, 44, 49, 55, 58, 58, 69, 70, 73, 76, 78, 81, 93]
复制