首页 > 代码库 > 桶排序

桶排序

桶排序的核心思想就是分治处理数据,把数据按照大小分发到各个区间(区间内数据保证有序,数据结构可以使用链表,方便分发过来的新数据插入)。

 

假设有N条数据是分布在一个固定的区间内(0,n),现在要对其排序,桶排序步骤如下

1 把(0,n)划分成m个区间,像这样 (0,n/m),(n/m+1, 2n/m),(2n/m+1,3n/m)...

2 遍历待排序的数据,把每个数字都按照大小分发到每个区间里面,保证插入有序

3 按照区间大小把每个区间的数据连接起来就好了

 

桶排序最好情况 : 待排数据完全均匀分布到m个区间内

桶排序最差情况 : 待排数据全部分配到一个区间内,这种情况就是对全数据做了插入排序

 

应用点:大数据的排序,比如有海量数据要进行排序,内存完全不够用,那么这时候就可以按照整数区间范围设定多个文件,再遍历海量待排数据,按照大小放入对应文件里面,再对文件内数据进行排序(假设划分合理,内存够),最后把各文件按照区间大小连接起来就好了

桶排序