一、桶排序
它同样是一种线性时间的排序算法，它类似于计数排序所创建的统计数组，桶排序需要创建若干个桶来协助排序。
每一个桶（bucket）代表一个区间范围，里面可以承载一个或多个元素。
如果有一个非整数数列如: 4.5，0.84，3.25，2.18，0.5
第1步，创建这些桶，并确定每一个桶的区间范围。
需要建立多少个桶，如何确定桶的区间范围，有很多种不同的方式。我们这里创建的桶数量等于原始数列的元素数量，除最后一个桶只包含数列最大值外，前面各个桶的区间按照比例来确定。
区间跨度=(最大值-最小值)/（桶的数量-1)
第2步，遍历原始数列，把元素对号入座放入各个桶中。
第3步，对每个桶内部的元素分别进行排序（只有第1个桶需要排序)。
第4步，遍历所有的桶，输出所有元素。
def bucketSort(ll):
# 1.得到数列的最大值,最小值
max = ll[0]
min = ll[0]
for i in range(1, len(ll)):
if ll[i] > max:
max = ll[i]
if ll[i] < min:
min = ll[i]
# 差值
diff = max - min
# print(diff)
# 2.初始化桶
bucket = []
for i in range(len(ll)):
bucket.append([]) #添加每个列表
print(bucket)
#3.遍历原数列，将每个元素放入桶中
for i in range(len(ll)):
#桶的索引
num=int((ll[i]-min)*(len(ll)-1)/diff)
#每个桶数列
bt=bucket[num]
# 将数据放入桶
bt.append(ll[i])
print(num,bt)
#4.每个桶内部排序
for i in range(len(bucket)):
bucket[i].sort()
print(bucket)
#5.排序
sort_list=[]
#循环输出排序的元素
for i in bucket:
for j in i:
sort_list.append(j)
return sort_list
if __name__ == '__main__':
ll=[4.5,0.84,3.25,2.18,0.5]
print(ll)
print(bucketSort(ll))
假设原始数列有n个元素，分成n个桶。
下面逐步来分析一下算法复杂度。
第1步，求数列最大值、最小值，运算量为n。
第2步，创建空桶，运算量为n。
第3步，把原始数列的元素分配到各个桶中，运算量为n。
第4步，在每个桶内部做排序，在元素分布相对均匀的情况下，所有桶的运算量之和为n。
第5步，输出排序数列，运算量为n。
因此，桶排序的总体时间复杂度为O (n)。 至于空间复杂度同样是O（n)。
总之，具有代表性的排序算法如下：
