直接看下方這張圖

作法：
步驟一：計算陣列值的範圍，確定計數陣列count的長度，計數陣列的長度len=max-min+1

步驟二：遍歷原陣列，填寫計數陣列，原陣列的元素arr[i]每出現一次，以arr[i]為索引的count陣列的元素加1

步驟三：遍歷計數陣列，計算累積頻次，這個累積頻次將對應於計數陣列索引（即待排序元素）在排序後陣列中的索引位置。累積頻次（累積計數陣列元素）的意義：累積頻次（也就是該元素）總比該元素索引在排序陣列中的索引位置大1，即表示原陣列中小於等於索引值的元素數目為“累積頻次”次。
出處

const {isSorted}=require('./utils');

function countingSort(arr){
  let max = arr[0];
  let min = arr[0];
  //Find the max value and min value first
  for (let index = 0; index < arr.length; index++){
    if (arr[index] > max){
      max = arr[index];
    }
    else if (arr[index] < min){
      min = arr[index];
    }
  }
  let range = max - min;
  let countingArray = [];
  //Default we set 0 to the empty countingArray.
  for (let i = 0; i <= range; i++){
    countingArray[i] = 0;

  }
  //Count the appearance frequency.
  for (let i = 0; i < arr.length; i++){
    countingArray[(arr[i] - min)]++;
  }
  
  let sortArrIndex = 0;
  let sortArr = new Array(arr.length);
  console.log('countingArray',countingArray)
  //If the value of the index in the countingArray is bigger than 0 ,put the sortArrIndex to the sortArr.
  for (let i = min; i <= max; i++){
    while (countingArray[i - min]-- > 0){
      console.log('i:',i)
      console.log('sortArrIndex',sortArrIndex)
      sortArr[sortArrIndex++] = i;
      console.log('sortArr',sortArr)
    }
  }
  return sortArr;
}
const arr=[4,4,1,7,9];
console.log(countingSort(arr));

完整程式碼