JS如何實現(xiàn)的計數(shù)排序與基數(shù)排序算法

這篇文章將為大家詳細講解有關JS如何實現(xiàn)的計數(shù)排序與基數(shù)排序算法，小編覺得挺實用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。

JS是什么

JS是JavaScript的簡稱，它是一種直譯式的腳本語言，其解釋器被稱為JavaScript引擎，是瀏覽器的一部分，主要用于web的開發(fā)，可以給網站添加各種各樣的動態(tài)效果，讓網頁更加美觀。

計數(shù)排序

計數(shù)排序就是簡單的桶排序，一個桶代表數(shù)組中一個數(shù)出現(xiàn)的個數(shù)，所以需要一個和數(shù)組數(shù)字范圍一樣大的輔助數(shù)組，一般用在范圍小于100的排序，時間復雜度為O(n)，空間復雜度為數(shù)組的數(shù)字范圍。

/**
 * 范圍在 start - end 之間的排序
 * 計數(shù)排序需要輔助數(shù)組，該輔助數(shù)組的長度是待排序數(shù)組的范圍，所以一般用作范圍小于100的排序
 */
function countSort(arr, start, end) {
  var len = arr.length;
  // 桶數(shù)組
  var suportArr = new Array(end - start + 1);
  // 結果數(shù)組
  var resArr = new Array(len);
  // 初始化桶數(shù)組
  for (i = 0; i < suportArr.length; i++) {
    suportArr[i] = 0;
  }
  // 待排序數(shù)組中的數(shù)組出現(xiàn)，在桶子對應位置+1代表這個數(shù)出現(xiàn)的個數(shù)+1了
  for (let i = 0; i < len; i++) {
    suportArr[arr[i]]++;
  }
   // 從第1項開始，桶數(shù)組加上前一個桶的個數(shù)，現(xiàn)在輔助數(shù)組的意義變成了每一項的排名了。
  for (let i = 1; i < suportArr.length; i++) {
    suportArr[i] += suportArr[i - 1];
  }
  // 根據輔助數(shù)組的排名，從后往前賦值
  for (let i = len - 1; i >= 0; i--) {
    resArr[suportArr[arr[i]] - 1] = arr[i];
    suportArr[arr[i]]--;
  }
  return resArr;
}

基數(shù)排序

基數(shù)排序是多躺的桶排序

var radix = 16; // 基數(shù)，可以為任何數(shù)，越大趟數(shù)越小，但是桶數(shù)越多，最好根據最大數(shù)字進行定義。
function _roundSort(arr, round, radix) {
  var buckets = new Array(radix);
  for (let i = 0; i < radix; i++) {
    buckets[i] = [];
  }
  // 將數(shù)組中的數(shù)放進對應的桶子中
  for (let i = 0; i < arr.length; i++) {
    let remainder = Math.floor(arr[i] / (radix ** (round - 1))) % radix;
    buckets[remainder].push(arr[i]);
  }
  // 將數(shù)組重新根據桶子進行排序
  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如何實現(xiàn)的計數(shù)排序與基數(shù)排序算法”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，使各位可以學到更多知識，如果覺得文章不錯，請把它分享出去讓更多的人看到。