iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 2
0

桶子排序法,在排序前,我們可以先準備數個桶子,而資料就像一個一個的球,每個桶子裝球數有限且區間固定,接下來就把球依照每個桶子不同的區間去做分類放置,如下圖。

假設raw data為[37,1,18,27,5,10,33,24,41],每個桶子能裝10個
桶子排序示意圖
圖片來自:https://jason-chen-1992.weebly.com/home/-sorting-algorithm

完整的程式碼如下:

function bucketSort (arr,bucketCapacity) {
  let bucketSortArray = [];
  
  //Get the min and max value at the first to calculate the bucket count.
  let min = Math.min.apply(Math,arr);
  let max = Math.max.apply(Math,arr);
  let bucketCount = Math.floor((max - min) / bucketCapacity)+1;
  
  //Initialize buckets object
  let buckets={};

  //The value of the key in the buckets object is an array means the bucket.
  for(let i = 0;i<bucketCount;i++){
    buckets[i]=[];
  };

  //Calculate the bucketIndex and put the value to the bucket in the buckets object.
  for (let i = 0; i < arr.length; i++) {
    let bucketIndex = Math.floor((arr[i] - min) / bucketCapacity);
    buckets[bucketIndex].push(arr[i]);
  };
  
  //Sort the array in buckets object and put the value to the bucketSortArray. 
  Object.keys(buckets).forEach((key)=> {
    buckets[key]=buckets[key].sort((a,b)=>a-b);
    bucketSortArray.push(...buckets[key]);
  });

  return bucketSortArray;
}

const arr=[37,1,18,27,5,10,33,24,41];
console.log(bucketSort(arr,10));

return [ 1, 5, 10, 18, 24, 27, 33, 37, 41 ]

完整程式碼


上一篇
JavaScript 演算法、資料結構第一章(目錄&簡介)
下一篇
氣泡排序法(Bubble Sort)
系列文
透過JavaScript學習演算法與資料結構30

尚未有邦友留言

立即登入留言