未加星标

JS实现的计数排序与基数排序算法示例

字体大小 | |
[前端(javascript) 所属分类 前端(javascript) | 发布者 店小二05 | 时间 | 作者 红领巾 ] 0人收藏点击收藏

本文实例讲述了JS实现的计数排序与基数排序算法。分享给大家供大家参考,具体如下:

计数排序

计数排序就是简单的桶排序,一个桶代表数组中一个数出现的个数,所以需要一个和数组数字范围一样大的辅助数组,一般用在范围小于100的排序,时间复杂度为O(n),空间复杂度为数组的数字范围。

/**
* 范围在 start - end 之间的排序
* 计数排序需要辅助数组,该辅助数组的长度是待排序数组的范围,所以一般用作范围小于100的排序
*/
function countSort(arr, start, end) {
var len = arr.length;
// 桶数组
var suportArr = new Array(end - start + 1);
// 结果数组
var resArr = new Array(len);
// 初始化桶数组
for (i = 0; i < suportArr.length; i++) {
suportArr[i] = 0;
}
// 待排序数组中的数组出现,在桶子对应位置+1代表这个数出现的个数+1了
for (let i = 0; i < len; i++) {
suportArr[arr[i]]++;
}
// 从第1项开始,桶数组加上前一个桶的个数,现在辅助数组的意义变成了每一项的排名了。
for (let i = 1; i < suportArr.length; i++) {
suportArr[i] += suportArr[i - 1];
}
// 根据辅助数组的排名,从后往前赋值
for (let i = len - 1; i >= 0; i--) {
resArr[suportArr[arr[i]] - 1] = arr[i];
suportArr[arr[i]]--;
}
return resArr;
}

基数排序

基数排序是多躺的桶排序

var radix = 16; // 基数,可以为任何数,越大趟数越小,但是桶数越多,最好根据最大数字进行定义。
function _roundSort(arr, round, radix) {
var buckets = new Array(radix);
for (let i = 0; i < radix; i++) {
buckets[i] = [];
}
// 将数组中的数放进对应的桶子中
for (let i = 0; i < arr.length; i++) {
let remainder = Math.floor(arr[i] / (radix ** (round - 1))) % radix;
buckets[remainder].push(arr[i]);
}
// 将数组重新根据桶子进行排序
var index = 0;
for (let i = 0; i < buckets.length; i++) {
for (let j = 0; j < buckets[i].length; j++) {
arr[index++] = buckets[i][j];
}
}
}
function radixSort(arr, round) {
for (let i = 1; i <= round; i++) {
_roundSort(arr, i, radix);
}
return arr;
}
console.log(radixSort([10,5,5,50,0,155,4622,5,1,4,2154], 4));

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

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

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

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

本文前端(javascript)相关术语:javascript是什么意思 javascript下载 javascript权威指南 javascript基础教程 javascript 正则表达式 javascript设计模式 javascript高级程序设计 精通javascript javascript教程

tags: arr,排序,数组,let,suportArr,JavaScript,lt,radix,i++,var,length,buckets,算法,round
分页:12
转载请注明
本文标题:JS实现的计数排序与基数排序算法示例
本站链接:http://www.codesec.net/view/569808.html
分享请点击:


1.凡CodeSecTeam转载的文章,均出自其它媒体或其他官网介绍,目的在于传递更多的信息,并不代表本站赞同其观点和其真实性负责;
2.转载的文章仅代表原创作者观点,与本站无关。其原创性以及文中陈述文字和内容未经本站证实,本站对该文以及其中全部或者部分内容、文字的真实性、完整性、及时性,不作出任何保证或承若;
3.如本站转载稿涉及版权等问题,请作者及时联系本站,我们会及时处理。
登录后可拥有收藏文章、关注作者等权限...
技术大类 技术大类 | 前端(javascript) | 评论(0) | 阅读(28)