這篇文章主要介紹了JS實現的計數排序與基數排序演算法,結合實例形式簡單分析了計數排序與基數排序的原理與JS實現技巧,對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));#以上就是這篇文章的所有內容了，希望可以給同學們帶來幫助！
相關推薦：
#以上是JS實現的計數排序與基數排序演算法範例_javascript技巧的詳細內容。更多資訊請關注PHP中文網其他相關文章！
