桶排序,利用编号分组存储数字,再利用编号合并分组的一种算法排序。
举个易于理解的例子:
一组数字,9,3,4,0,2,8,5,1,7,6,11,10,18,15,17,12,16,13,19,14
我们把这组数字分组编号成10个桶装起来,但怎么编号分组呢?
这里我们利用数字范围来对数字进行分桶。首先,最大数减去最小数,获取这组数字的取值范围,然后,我们让这个取值范围除以桶数,获取一个桶的取值范围,既然知道一个桶的取值范围,那么,通过对比每个数字占用多少个桶,我们就可以获取这个数字所对应的桶的编号了。(换一句话说,就是每个数字占用多少个取值范围,这里的桶其实就是数字的取值范围的具体化东西)
利用上面的例子做解释:
上面的最大值是19,最小值是0,所以这组数的取值范围是: 19-0=19。
我们要用10个桶来分装这组数字,则一个桶的取值范围是: 19 / 10 = 1.9。
所以,一个桶的取值范围就是: 1.9。
知道了这些之后,我们怎么知道每个数字所对应的桶的编号呢?
我们让每个数字减去最小值再除以一个桶的取值范围就可以获得这个数字所对应的桶编号了,为什么这么说呢?因为我们就是利用数值范围来分桶的,所以理所当然的也是获取每个数字的取值范围来分桶的编号,而最小值就是我们的取值标准,当然是要每个数字都减去它才能准确的获取每个数的取值范围了。
根据上面的解释,那么,第一个数字的桶编号就是: (9-0) / 1.9 = 4.7368·······
当然为了确保编号为整数,我们必须给编号取整,这里我们是向上取整,所以第一个数:9的桶编号就是5啦。
其他的数字获取桶编号都是同样的原理,这里就不再重复叙述了。
下面是js程序的实现:
桶排序