用于基数排序算法的基数大小在实践中是否重要？
Does the radix size used for radix sort algorithm matter in a practice?
我听说基数排序的最坏内存情况是 O(n+r)，其中 n 是数组大小，r 是基数。但是由于在计算中很少使用超过 16 进制的任何东西，所以在实践中 r=2 还是 r=100 真的很重要吗？对space有什么实际影响吗？
那应该是最坏的情况 space O(n + r logr(range))，其中 range 是要排序的值的范围。例如，对于 64 位整数范围 = 2^64，如果对 64 位整数进行基于 256 的基数排序，则 log256(2^64) = 8，这是所需的基数排序遍数。最坏的情况 space 用法是使用所有通道的矩阵，例如用于对 64 位无符号整数进行排序的 8 x 256 矩阵 base 256：matrix[8][256]。最坏情况 space 开销是用于基数排序的临时数组的大小 = n 个元素加上矩阵的大小。对于以 256 为基数排序的 64 位整数的示例：
n + r · ceil(log256(2^64)) = n + 256 · 8.
我听说基数排序的最坏内存情况是 O(n+r)，其中 n 是数组大小，r 是基数。但是由于在计算中很少使用超过 16 进制的任何东西，所以在实践中 r=2 还是 r=100 真的很重要吗？对space有什么实际影响吗？
那应该是最坏的情况 space O(n + r logr(range))，其中 range 是要排序的值的范围。例如，对于 64 位整数范围 = 2^64，如果对 64 位整数进行基于 256 的基数排序，则 log256(2^64) = 8，这是所需的基数排序遍数。最坏的情况 space 用法是使用所有通道的矩阵，例如用于对 64 位无符号整数进行排序的 8 x 256 矩阵 base 256：matrix[8][256]。最坏情况 space 开销是用于基数排序的临时数组的大小 = n 个元素加上矩阵的大小。对于以 256 为基数排序的 64 位整数的示例：
n + r · ceil(log256(2^64)) = n + 256 · 8.