我一直在研究各种排序算法，有一个叫radix sort的算法，我必须对基数2^(lg n)的数字进行排序，但我不知道这到底是什么。我的意思是我知道基数2是二进制的，但是对于对数n我就不太明白了。
所以我想知道基数2^(lg n)到底是什么，以及它会以何种方式影响我的代码。
这个问题缺少的信息是：lg()的基数是什么：如果n是最大范围的值，或者如果n是元素的数量。另外，语句中还应该有一个上限（四舍五入分数到下一个整数）函数。
假设n是最大取值范围，其中n=max()+1-min()。
如果lg = log2, 那么就是2^(ceil(log2(n))), 也就是n或2的下一个次幂> 如果n不是2的次幂, 那么就是n. 如果对数字进行排序, 还不如用计数排序代替半径排序.
如果lg=log4，那么就是2^(ceil(log4(n)))。例如，如果n=1024，那么2^(ceil(log4(1024)))==2^5==32，需要进行2次radix排序(通常是先进行最小有效数字排序)才能对数据进行排序。
如果lg=log16，那么就是2^(ceil(log16(n)))。例如，如果n=65536，那么2^(ceil(log16(65536)))==2^4==16，将需要4个radix sort passes来排序数据。
另外，在典型的 PC (X86 处理器)上，如果在 32 位或 64 位无符号整数上使用 radix 排序，使用 2^8 == 256 通常是最快的，尽管这比使用 2^16 == 65536 这样的方法意味着更多的次数。
lg n这个符号是对数的速记。2 n.
既然如此，你能不能把2lg n = 2原木2 n?