文章目录
九、桶排序十、基数排序九、桶排序
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()# 回填,这里桶内部排序直接调用了sortedfor 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]
十、基数排序
1、基数介绍
基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数。
2、基数排序、计数排序和桶排序的差异
这三种排序算法都利用了桶的概念,但对桶的使用方法上有明显差异:
基数排序:根据键值的每位数字来分配桶;
计数排序:每个桶只存储单一键值;
桶排序:每个桶存储一定范围的数值;
3、动图演示
4、Python练习
def RadixSort(list):i = 0#初始为个位排序n = 1 #最小的位数置为1(包含0)max_num = max(list) #得到带排序数组中最大数while max_num > 10**n: #得到最大数是几位数n += 1while 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 = 0for k in range(10):if len(bucket[k]) != 0: #若桶不为空for y in bucket[k]: #将该桶中每个元素list[j] = y #放回到数组中j += 1i += 1return list
文章转载于:
十大经典排序算法(Python)