8. 计数排序

算法描述

1. 统计数组中每个值为 i 的元素出现的次数，存入统计数组 C 的第 i 项
2. 依次将统计数组 C 中值 val 不为 0 的下标推入到结果数组，推入 val 次

动图演示

算法实现

/**
 * 计数排序
 * @param {number[]} arr 数组
 */
const countingSort = (arr) => {
  const count = []
  for (let i = 0; i < arr.length; i++) {
    if (!count[arr[i]]) count[arr[i]] = 0
    count[arr[i]] += 1
  }
  const result = []
  for (let i = 0; i < count.length; i++) {
    if (count[i]) {
      for (let j = 0; j < count[i]; j++) {
        result.push(i)
      }
    }
  }
  return result
}

当输入 n 个 0～k 之间的整数时，时间复杂度为 o(n+k)，空间复杂度为 o(n+k)。