sorting - 用于基数排序算法的基数大小在实践中是否重要？

Question

我听说基数排序的最坏情况下的内存情况是 O(n+r)，其中 n 是数组大小，r 是基数。但是由于在计算中很少使用超过基数 16 的任何东西，所以在实践中 r=2 或 r=100 真的很重要吗？对空间有什么真正的影响吗？

标签： sortingmemoryradix-sort

Answer 1

这应该是最坏情况空间 O(n + r logr(range))，其中 range 是要排序的值的范围。例如，对于 64 位整数范围 = 2^64，如果对 64 位整数进行基数排序基数 256，则 log256(2^64) = 8，这是所需的基数排序次数。最坏的空间使用情况是使用所有通道的矩阵，例如用于对 64 位无符号整数进行排序的 8 x 256 矩阵，以 256 为基数：matrix[8][256]。最坏情况下的空间开销是用于基数排序的临时数组的大小 = n 个元素加上矩阵的大小。对于以 256 为基数排序的 64 位整数的示例：

n + r · ceil(log256(2^64)) = n + 256 · 8.