JS实现的计数排序与基数排序算法示例
程序员文章站
2022-06-25 13:28:39
本文实例讲述了js实现的计数排序与基数排序算法。分享给大家供大家参考,具体如下:
计数排序
计数排序就是简单的桶排序,一个桶代表数组中一个数出现的个数,所以需要一个和数...
本文实例讲述了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:这里再为大家推荐一款关于排序的演示工具供大家参考:
在线动画演示插入/选择/冒泡/归并/希尔/快速排序算法过程工具:
更多关于javascript相关内容感兴趣的读者可查看本站专题:《javascript数学运算用法总结》、《javascript数据结构与算法技巧总结》、《javascript数组操作技巧总结》、《javascript排序算法总结》、《javascript遍历算法与技巧总结》、《javascript查找算法技巧总结》及《javascript错误与调试技巧总结》
希望本文所述对大家javascript程序设计有所帮助。
下一篇: linux 操作 ftp 常用命令