JS桶排序的简单理解与实现方法示例

2023-08-07 11:47:04 67

本文实例讲述了JS桶排序的简单理解与实现方法。分享给大家供大家参考，具体如下：

桶排序，利用编号分组存储数字，再利用编号合并分组的一种算法排序。

举个易于理解的例子：

一组数字，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程序的实现：





桶排序





//桶排序,参数数组,桶的个数，这里用数组模拟桶
varcask=function(arr,caskCount){
//不是数组，返回false
if(toString.call(arr)!='[objectArray]'){
returnfalse;
}
//获取数组的长度
varlen=arr.length;
if(len<=1){
returnarr;//长度小于等于1不用排序
}
varlist=[],//装桶的桶，用它来控制存储桶的编号
result=[],//返回的结果
max=arr[0],
min=arr[0];
//默认桶的个数为10
varcaskCount=parseInt(caskCount)>0?parseInt(caskCount):10;
//获取数组的最大值和最小值
for(vari=1;i=min?min:arr[i];
}
//分成caskCount个桶，桶所占用的范围
varrange=(max-min)/caskCount;
for(vari=0;i=0&&list[index][k]>arr[i]){
//桶前面的数字放到后面去
list[index][k+1]=list[index][k];//第一个k+1为新增的桶
//小的提前一个位置
//list[index][k]=arr[i];
k--;
}
//不用排序的，直接加在桶的最后面
list[index][k+1]=arr[i];
}else{
//没有值则生成桶，并把值放到对应的桶中
list[index]=[];
list[index][0]=arr[i];
}
}
//合并桶
varn=0;
while(n<=caskCount){
if(list[n]){
result=result.concat(list[n]);
}
n++;
}
returnresult;
}
vararr=[8,39,400,500,3,4,20,44,440];
alert(cask(arr,10));
//alert(parseInt(-1)?parseInt(-1):1);

感兴趣的朋友可以使用在线HTML/CSS/JavaScript代码运行工具：http://tools.jb51.net/code/HtmlJsRun测试上述代码运行效果。

PS：这里再为大家推荐一款关于排序的演示工具供大家参考：

在线动画演示插入/选择/冒泡/归并/希尔/快速排序算法过程工具：
http://tools.jb51.net/aideddesign/paixu_ys

更多关于JavaScript相关内容感兴趣的读者可查看本站专题：《JavaScript数学运算用法总结》、《JavaScript数据结构与算法技巧总结》、《JavaScript数组操作技巧总结》、《JavaScript排序算法总结》、《JavaScript遍历算法与技巧总结》、《JavaScript查找算法技巧总结》及《JavaScript错误与调试技巧总结》

希望本文所述对大家JavaScript程序设计有所帮助。

声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。

JS桶排序的简单理解与实现方法示例

热门推荐

随机推荐