原理是將陣列分到有限數量的桶裡
每個桶再個別排序（有可能再使用別的排序演算法或是以遞迴方式繼續使用桶排序進行排序）

arr = [1, 4, 2, 3, 5, 7, 8, 6, 9]

def bucket_sort(array, bucket_size = 5)
  if array.empty?
    return
  end

  max_value = array.max
  min_value = array.min
  bucket_count = ((max_value - min_value) / bucket_size).floor + 1

  # create buckets
  buckets = []
  bucket_count.times { buckets.push [] }

  # fill buckets
  array.each do |item|
    buckets[((item - min_value) / bucket_size).floor].push(item)
  end

  # sort buckets
  (0..buckets.size - 1).each do |i|
    selection_sort buckets[i]
  end

  buckets.flatten
end


def selection_sort(array)
  n = array.size - 1
  n.times do |index|
    temp_item, temp_index = array[index], index
      for i in index...array.size
        temp_item, temp_index = array[i], i if array[i] < temp_item
      end
    array[index], array[temp_index] = array[temp_index], array[index]
  end
  array
end

pp bucket_sort(arr)

const arr = [1, 4, 2, 3, 5, 7, 8, 6, 9]

function bucketSort (array, bucket_size = 5) {
    let bucketSortArray = []

    let maxValue = Math.max.apply(Math,arr)
    let minValue = Math.min.apply(Math,arr)
    let bucketCount = Math.floor((maxValue - minValue) / bucket_size) + 1

    // create buckets
    let buckets = {}
    for(let i = 0; i < bucketCount; i++) {
        buckets[i] = []
    }

    // fill buckets
    for (let i = 0; i < arr.length; i++) {
        let bucketIndex = Math.floor((arr[i] - minValue) / bucket_size)
        buckets[bucketIndex].push(array[i])
    }

    // sort buckets
    Object.keys(buckets).forEach((key) => {
        bucketSortArray.push(selectionSort(buckets[key]))
    })

    return bucketSortArray.flat()
}

const selectionSort = (array) => {
  const count = array.length;
  for (let i = 0; i < count; i++) {
      let min = i;
      for (let j = i + 1; j < count; j++) {
          if (array[j] < array[min]) {
              min = j;
          }
      }
      if (min !== i) {
          let temp = array[i];
          array[i] = array[min];
          array[min] = temp;
      }
  }
  return array;
}

console.log(bucketSort(arr))