2020-01-29 计数排序

function countingSort(arr) {
  const len = arr.length
  if (len <= 1) return arr

  const max = getMaxVal(arr)
  const counts = Array(max + 1).fill(0)

  // 计算每个元素的个数，放入到counts桶中
  // counts下标是元素，值是元素个数
  arr.forEach(ele => {
    counts[ele]++
  })

  let sortedIndex = 0
  counts.forEach((count, i) => {
    while (count-- > 0) {
      arr[sortedIndex++] = i
    }
  })

  return arr
}

function getMaxVal(arr) {
  let max = arr[0]
  for (let i = 1; i < arr.length; i++) {
    (arr[i] > max) && (max = arr[i])
  }

  return max
}