算法之排序算法——桶排序
一、基本思想
划重点：划分多个范围相同的区间，每个区间自排序，最后合并。
桶排序是计数排序的扩展版本，计数排序可以看成每个桶只存储相同元素。
桶排序保证每个桶存储一定范围，通过映射函数，将待排序数组中的元素映射到各个对应的桶中。
取值范围要合理保证元素分布均匀。
对每个桶中的元素进行排序，最后将桶合并，完成有序排列。
二、图解过程
a、待排序序列
b、划分到五个桶
c、桶里自排序
d、合并，完成有序序列
三、核心代码
#待排序序列list = [24,5,37,52,69,55,8,6,44,53]#划五个桶bucket=[[],[],[],[],[]]#划分到五个桶for i in list:if i >0 and i <= 20:bucket[0].append(i)elif i >20 and i <= 40:bucket[1].append(i)elif i >40 and i <= 60:bucket[2].append(i)elif i >60 and i <= 80:bucket[3].append(i)elif i >80 and i <= 100:bucket[4].append(i)result=[]#桶内自排序并合并，现简化用list.sort()方法#一般用快速排序法for i in bucket:i.sort()result = result+i#完成print(result)
#输出[5, 6, 8, 24, 37, 44, 52, 53, 55, 69]
四、复杂度分析
1. 时间复杂度：O(N + M)
对于待排序序列大小为 N，共分为 M 个桶
当使用快速排序算法，平均时间复杂度:
O(N)+O(M∗(N/M∗log(N/M)
2. 空间复杂度：O(N + M)
五、稳定性分析
桶排序的稳定性取决于桶内排序使用的算法。