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));