iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 10
0

直接看下方這張圖
圖

作法:
步驟一:計算陣列值的範圍,確定計數陣列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));

完整程式碼


上一篇
堆積排序法(Heap Sort)
下一篇
基數排序法(Radix Sort LSD mode)
系列文
透過JavaScript學習演算法與資料結構30

尚未有邦友留言

立即登入留言