计数排序
- 找到给定序列的最小值与最大值
- 创建一个长度为最大值-最小值+1的数组，初始化都为0
- 然后遍历原序列，并为数组中索引为当前值－最小值的值＋１
- 此时数组中已经记录好每个值的数量，自然也就是有序的了
例如：
计数排序实现
下面为列表的计数排序
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
def count_sort(s): """计数排序""" # 找到最大最小值 min_num = min(s) max_num = max(s) # 计数列表 count_list = [0]*(max_num-min_num+1) # 计数 for i in s: count_list[i-min_num] += 1 s.clear() # 填回 for ind,i in enumerate(count_list): while i != 0: s.append(ind+min_num) i -= 1if __name__ == '__main__': a = [3,6,8,4,2,6,7,3] count_sort(a) print(a) |
计数排序的缺点
当数值中有非整数时，计数数组的索引无法分配
桶排序
桶排序原理：
- 桶排序与计数排序类似，但可以解决非整数的排序
- 桶排序相当于把计数数组划分为按顺序的几个部分
- 每一部分叫做一个桶，它来存放处于该范围内的数
- 然后再对每个桶内部进行排序，可以使用其他排序方法如快速排序
- 最后整个桶数组就是排列好的数据，再将其返回给原序列
举例：
桶排序实现
这里选择桶的数量为序列元素个数+1，范围分别是5等分与最大值，和上面那个图一样。
具体问题应该按照具体情况进行桶划分
这里桶内部排序直接调用了sorted
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
def bucket_sort(s): """桶排序""" min_num = min(s) max_num = max(s) # 桶的大小 bucket_range = (max_num-min_num) / len(s) # 桶数组 count_list = [ [] for i in range(len(s) + 1)] # 向桶数组填数 for i in s: count_list[int((i-min_num)//bucket_range)].append(i) s.clear() # 回填，这里桶内部排序直接调用了sorted for i in count_list: for j in sorted(i): s.append(j)if __name__ == '__main__': a = [3.2,6,8,4,2,6,7,3] bucket_sort(a) print(a) # [2, 3, 3.2, 4, 6, 6, 7, 8] |
总结
计数排序与桶排序都是以牺牲空间换时间，虽然很快，但由于可能产生大量的空位置导致内存增大，尤其是计数排序。
桶排序中尽量使每个桶中的元素个数均匀分布最好
以上所述是小编给大家介绍的python计数排序与桶排序详解整合，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对服务器之家网站的支持！
原文链接：https://www.cnblogs.com/sfencs-hcy/p/10612422.html
