【动手学数据结构—计数桶排序（Python）】

计数/桶排序

• 原理
• 代码实现

原理

当排序的数据比较多的时候，需要统计所有数出现的次数，它的空间复杂度为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)