桶排序算法思想
桶排序的思想是把[0,1)划分为n个大小相同的子区间,每一子区间是一个桶。然后将n个记录分配到各个桶中。因为关键字序列是均匀分布在[0,1)上的,所以一般不会有很多个记录落入同一个桶中。由于同一桶中的记录其关键字不尽相同,所以必须采用关键字比较的排序方法(通常用插入排序)对各个桶进行排序,然后依次将各非空桶中的记录连接(收集)起来即可。
例如要对大小为[1..1000]范围内的n个整数A[1..n]排序,可以把桶设为大小为10的范围,具体而言,设集合B[1]存储[1..10]的整数,集合B[2]存储(10..20]的整数,……集合B[i]存储((i-1)10, i10]的整数,i = 1,2,..100。总共有100个桶。然后对A[1..n]从头到尾扫描一遍,把每个A[i]放入对应的桶B[j]中。 然后再对这100个桶中每个桶里的数字排序,这时可用冒泡,选择,乃至快排,一般来说任何排序法都可以。最后依次输出每个桶里面的数字,且每个桶中的数字从小到大输出,这样就得到所有数字排好序的一个序列了。
最坏情况时间复杂度:当分布不均匀时,全部元素都分到一个桶中,则O(n^2);最好情况分到不同的桶时间复杂度O(n);桶排序的平均时间复杂度是线性的,即 O(n)。 。