不为成仙,只为在这红尘中等你回来。

您现在的位置是:网站首页>>算法与数据结构

桶排序

2020年11月7日 13:24 | 分类:算法与数据结构 | 标签: Python

  • 在计数排序中,如果元素的范围比较大(比如在1到1亿之间),如何改造算法?
  • 桶排序(Bucket Sort):首先将元素分在不同的桶中,在对每个桶中的元素排序。
  • 桶排序的表现取决于数据的分布。也就是需要对不同数据排序时采取不同的分桶策略。

桶排序图解

def bucket_sort(lst, n=100, max_num=10000):
    buckets = [[] for _ in range(n)]  # 创建桶
    for val in lst:
        i = min(val // (max_num // n), n - 1)  # i 表示 val 放到几号桶
        buckets[i].append(val)  # 把 val 加到桶里面
        # 保持桶内的顺序
        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]

    sorted_lst = []
    for buc in buckets:
        sorted_lst.extend(buc)
    return sorted_lst

import random

lst = [random.randint(0, 1000) for _ in range(1000)]

print(bucket_sort(lst))