时间和空间复杂度

时间复杂度：

• O(n + k)
  • 其中，n 是元素数量，k 是值的范围（max + 1）。遍历一次进行计数，再遍历一次计数结果以重建数组。
• 当 k 较小且固定时，实际复杂度为 O(n)，比比较排序的 O(n log n) 更快。

空间复杂度：

• O(n + k)
  • 计数数组占用 O(k) 空间，输出占用 O(n) 空间。

总结：

• 计数排序是一种稳定的非比较排序，在整数范围较小时可以在线性时间内运行。
• 当值的范围 k 非常大时，计数数组会很大，因此计数排序不适合这种情况。这个版本假设整数为非负数。