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

 

You May Also Like