上篇文章我们学习了算法入门——归并排序、希尔排序，这篇文章我们学习算法入门——计数排序、桶排序、基数排序。
计数排序
计数排序是已知列表元素的范围，统计列表元素出现的频次，再进行排序，例如：
li=[2,5,2,7,7,7,8]
在上面的列表中，元素2出现了两次，5出现了一次，7出现了三次，8出现了一次，再通过元素出现的次数来输出列表，示例代码如下：
def count_sort(li,max_count):
print('排序前：',li)
count=[0 for _ in range(max_count+1)] # 长度为max_count，值全为0的列表
for val in li: # 遍历列表的值
count[val]+=1 # 计数
li.clear() # 清空列表
print('统计列表元素出现的次数',count) # 输出count列表
for index,val in enumerate(count): # 遍历列表的
for i in range(val): # 根据count列表的值来遍历几次
li.append(index) # 添加元素
li=[3,5,2,5,1,1,6,10,9,8]
count_sort(li,10)
print('排序后',li)
运行结果如下图所示：
因为列表的下标是从0开始的，所以统计列表元素出现的次数为0出现了0次，1出现了2次，2出现了一次，3出现了1次等等。
计数排序的缺点：
- 消耗大量内存；
- 需要知道要排序的列表最大值；
桶排序
桶排序算是计数排序的升级版，桶排序首先把元素分在不同的桶中，再对每个桶中元素排序。如下图所示：
其实每个桶表示一个空列表，示例代码如下：
def bucket_sort(li, n=4, max_num=40):
buckets = [[] for _ in range(n)] # 创建桶
for var in li:
i = min(var // (max_num // n), n - 1) # i 表示元素放在哪个桶
buckets[i].append(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
li=[35,22,12,19,20,5,10,15]
print(bucket_sort(li))
运行结果如下：
基数排序
基数排序是根据元素位数进行排序，例如，先按照元素的个位数来排序，按照元素的十位数来排序，再按照百位、千位等等。如下图所示：
示例代码如下：
def radix_sort(li):
max_num = max(li) # 获取列表最大值
it = 0
# 根据最大值来判断进行元素的个位、百位、千位、万位来排序
while 10 ** it <= max_num:
buckets=[[] for _ in range(10)] # 创建空列表
for var in li:
digit=(var//10**it)%10
buckets[digit].append(var) # 插入空列表中
li.clear()
for buc in buckets:
li.extend(buc) # 合并
it += 1
print(li)
li=[22,54,28,32,14,33,56,12]
radix_sort(li)
运行结果如下：
好了，关于算法入门——计数排、桶排序、基数排序就学到这里了，下篇文章学习算法入门的其他知识。
公众号：白巧克力LIN
该公众号发布Python、数据库、Linux、Flask、自动化测试、Git、算法等相关文章！
