备战蓝桥杯Day23-桶排序

桶排序

在计数排序的基础上，如果元素的范围较大（比如在1-1亿之间），如何改造算法？

那么就引出桶排序（Bucket Sort）：首先将数据分为不同的桶，再把元素放到相应的桶中，再对桶中的元素进行排序。

排序思路

1. 分桶： 将待排序数据根据某种规则分配到不同的桶中。可以根据数值范围、数据的某个特征等来确定分桶规则。

2. 桶内排序： 对每个桶内的数据进行排序。可以使用任何适合的排序算法，通常是插入排序或者快速排序。

3. 合并： 将所有桶的结果按顺序合并，即可得到最终有序序列。

代码实现 

def bucket_sort(li, n=100, max_num=10000):
    buckets = [[] for _ in range(n)]
    for var in li:
        i = min(var//(max_num//n), n-1)  # 下面有详细注释
        buckets[i].append(var)  # 把var放到桶里
        # 保持桶内的顺序
        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(0,10000) for i in range(1, 1000000)]
li = bucket_sort(li)
print(li)

 一些注释

 i = min(var//(max_num//n), n-1)

n:有几个桶

max_num:数据元素的总个数

max_num // n:每个桶里有几个数

var // (max_num // n):把循环遍历到的数var应该放到哪个桶里

min(var // (max_num // n))遍历到最后一个数时，桶会出现越界的情况，为了避免这种情况，我们总是与n-1比较并取最小值，这样不会出现越界的情况。

数据非常大跑代码会有点慢，耐心等待一下~

运行结果

只截取了开头结尾，数据太多了没截全。