- 原理
- 代码实现
当排序的数据比较多的时候，需要统计所有数出现的次数，它的空间复杂度为o(n)。桶排序的优点在与优化了内存的使用，实际上桶排序的算法效率并不高，因为有两层for嵌套，如果数据分布比较不理想的时候，时间复杂度可达o(n^2)
import random
def count_sort(li, max):
count = [0 for _ in range(max+2)] # 初始计数都为0
for i in li:
count[i] += 1
li.clear() # 清楚li列表
for idx, value in enumerate(count):
li.extend([idx] * value)
def bucket_sort(li, max, n=100): # n:桶的个数
# 构建桶
buckets = [[] for _ in range(n)]
for i in li:
bucket_num = min(i // (max // n), n-1) # 代表放到几号桶 最小为0
buckets[bucket_num].append(i)
# 下面顺便进行每个桶的冒泡排序
# 比如任意一个桶 [1, 3, 4, 2] 2是加进来的，先和4比较，如果小于4，则两者替换
for j in range(len(buckets[bucket_num])-1, 0, -1):
if buckets[bucket_num][j] < buckets[bucket_num][j-1]:
buckets[bucket_num][j], buckets[bucket_num][j-1] = buckets[bucket_num][j-1], buckets[bucket_num][j]
else:
break
sort_list = []
for l in buckets:
sort_list.extend(l)
return sort_list
Li = [random.randint(0, 300) for _ in range(16)]
print(Li)
print('计算排序...')
count_sort(Li, 300)
print(Li)
li = bucket_sort(Li, 300)
print('桶排序...')
print(li)
