桶排序是将给定的一组元素根据其范围划分成若干个有序的子区间,将给定的元素按照某种关系放到某一个子区间中,再将子区间中的元素按某种算法排序,最后依次将每个子区间的元素依次取出,组合成有序的元素。
举个例子,假设给定一组数字4,16,8,2,5,11,1,7,13,10,7
假设我们这里桶的数量是4个,实际需要根据资源的情况选择桶的数量。
然后我们需要选择某种算法,让上面的数字尽可能均匀的落到每个桶中,这里演示就简单点,桶号=(值-1)对桶数求商。
遍历给定的数字,第1个是数字4,(4 - 1) / 4 = 0,所以数字4应当放到桶0中
第2个数字16的桶号是(16 - 1) / 4 = 3,所以数字16放到桶3中
第3个数字8的桶号是(8 - 1) / 4 = 1,所以数字8放到桶1中
第4个数字2的桶号是(2 - 1) / 4 = 0,所以数字2放到桶0中,桶0中已经有了一个数字4了,我们在落桶的同时可以对其排序,也可以所有数组都落入桶后,再对桶内的数字排序,这里在落桶的同时用插入排序对桶内的元素排序,大的放上面,小的放下面
第5个数字5的桶号是(5 - 1) / 4 = 1,所以数字5放到桶1中,桶1中也已经有一个数字了,所以数字5落桶后用插入排序对桶1内的数字排序
第6个数字11的桶号是(11 - 1) / 4 = 2,所以数字11放到桶2中
第7个数字1的桶号是(1 - 1) / 4 = 0,所以数字1放到桶0中,同样,放入后需要排序
第8个数字7的桶号是(7 - 1) / 4 = 1,所以数字7放到桶1中
第9个数字13的桶号是(13 - 1) / 4 = 3,所以数字13放到桶3中
第10个数字10的桶号是(10 - 1) / 4 = 2,所以数字10放到桶2中
第11个数字7的桶号是(7 - 1) / 4 = 1,所以数字7放到桶1中
这样,所有的数字都落桶完成了,桶中的数字也是有序的,接下来将所有的桶按序号从小到大,桶中的数字从下到上依次取出,得到排序后的数字
总结
- 桶排序一般用于元素分布比较均匀的情况,如果元素分布十分不均匀,或者范围比较大,则可能不太适合桶排序
- 桶排序的空间复杂度和时间复杂度和桶的数量,使用的排序算法有关,应用中要根据实际情况选择。