九、桶排序
1、桶排序介绍
桶排序是计数排序的升级版。它利用了函数的映射关系,高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效,我们需要做到这两点:
在额外空间充足的情况下,尽量增大桶的数量
使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中
同时,对于桶中元素的排序,选择何种比较排序算法对于性能的影响至关重要。
2、桶排序最快与最慢
- 最快的时候:当输入的数据可以均匀的分配到每一个桶中。
- 最慢的时候:当输入的数据被分配到了同一个桶中。
3、Python练习
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()
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)
十、基数排序
1、基数介绍
基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数。
2、基数排序、计数排序和桶排序的差异
这三种排序算法都利用了桶的概念,但对桶的使用方法上有明显差异:
-
基数排序:根据键值的每位数字来分配桶;
-
计数排序:每个桶只存储单一键值;
-
桶排序:每个桶存储一定范围的数值;
3、动图演示
4、Python练习
def RadixSort(list):
i = 0
n = 1
max_num = max(list)
while max_num > 10**n:
n += 1
while i < n:
bucket = {}
for x in range(10):
bucket.setdefault(x, [])
for x in list:
radix =int((x / (10**i)) % 10)
bucket[radix].append(x)
j = 0
for k in range(10):
if len(bucket[k]) != 0:
for y in bucket[k]:
list[j] = y
j += 1
i += 1
return list
文章转载于:
十大经典排序算法(Python)
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)