本文实例讲述了 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;
- }
基数排序是多躺的桶排序
PS:这里再为大家推荐一款关于排序的演示工具供大家参考:
- 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));
在线动画演示插入 / 选择 / 冒泡 / 归并 / 希尔 / 快速排序算法过程工具: http://tools.jb51.net/aideddesign/paixu_ys
更多关于 JavaScript 相关内容感兴趣的读者可查看本站专题:《 JavaScript 数学运算用法总结 》、《 JavaScript 数据结构与算法技巧总结 》、《 JavaScript 数组操作技巧总结 》、《 JavaScript 排序算法总结 》、《 JavaScript 遍历算法与技巧总结 》、《 JavaScript 查找算法技巧总结 》及《 JavaScript 错误与调试技巧总结 》
希望本文所述对大家 JavaScript 程序设计有所帮助。
来源: http://www.jb51.net/article/129716.htm