文章目录
九、桶排序十、基数排序九、桶排序
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）
