时间和空间复杂度

时间复杂度：

• O(d * (n + k))
  • 其中，n 是元素的数量，k 是基数（10），d 是最大值的位数。每一轮共进行 d 轮，每轮需要 O(n + k) 的工作量。
• 当 d 较小且固定时，它的表现类似于 O(n)，比比较排序的 O(n log n) 更快。

空间复杂度：

• O(n + k)
  • 每一轮都会构建一个大小为 n 的输出数组和一个大小为 k 的计数数组。

总结：

• 基数排序是一种稳定的非比较排序，对于位数有限的整数键，其速度可以超过 O(n log n)。
• 它要求键可以拆分为数字，并且需要一些额外内存；此版本假设整数为非负数。