桶排序算法

桶排序（又称箱排序）是一种基于分治思想、效率很高的排序算法，其核心思想是，讲数据依次放入顺序摆放的若干个桶内，然后每个桶内元素再进行排序，完后成将桶内元素合并，得到最终排序结果。

桶排序算法在稀疏数列中，表现不好，但它是下一篇文章要介绍的基数排序算法的底层原理。

代码示例

import math
def bucket_sort(arr, cell_num=20, max_num=100):
    # 桶的数量
    bucket_num = math.ceil(max_num / cell_num)
    buckets = [[] for _ in range(bucket_num)]
    # 计算属于那个桶，并添加 0-49 50-99 ...
    for i in arr:
        idx = min(i // cell_num, bucket_num - 1)
        buckets[idx].append(i)
        # 排序
        for j in range(len(buckets[idx])-1, 0, -1):
            if buckets[idx][j] < buckets[idx][j-1]:
                buckets[idx][j] , buckets[idx][j-1] = buckets[idx][j-1] , buckets[idx][j]
    arr.clear()
    for bc in buckets:
        arr.extend(bc)

lst = [35, 30, 32, 90, 86, 33]
bucket_sort(lst)
print(lst)