计数排序

计数排序不比较元素大小，而是统计每个值出现的次数，再按照值的顺序恢复结果。它适合整数范围较小的数据。

实现

js

function countingSort(arr) {
  if (arr.length === 0) return []

  const min = Math.min(...arr)
  const max = Math.max(...arr)
  const counts = Array(max - min + 1).fill(0)

  for (const value of arr) counts[value - min]++

  const result = []
  counts.forEach((count, offset) => {
    for (let i = 0; i < count; i++) result.push(offset + min)
  })

  return result
}

复杂度

设数据范围为 k：

时间复杂度：O(n + k)
空间复杂度：O(k)
稳定性：上面的实现对相同整数保持等价顺序；扩展到对象时需要额外设计

当 k 远小于 n² 且数据为整数时，计数排序可以达到很高的效率；如果数值范围过大，空间成本会明显增加。