我在考虑线性时间排序问题，它出现在很多来源中，它提示您在线性时间内对从 0 到 n^3-1 范围内的数字数组进行排序。
因此，一种方法是使用通常在 O(wn) 中运行的基数排序，其中 w 是最大字大小，通过观察我们可以通过使用基 3 获得该范围内任何数字的字大小 n 。
这就是我的问题 - 虽然在纸上看起来不错，但实际上将所有数字转换为基础 n 天真的方法将花费相当多的时间，甚至可能比后来的排序本身还要多。有什么方法可以比天真地更快地转换为基础 n 或者以某种方式欺骗自己摆脱这种限制，或者您是否只需要忍受它？
最佳答案
一个有用的观察结果是，如果您选择的基数不是 n，而是大于或等于 n 的 2 的最小幂作为基数，则该算法的运行时间是相同的。让我们假设这个数字是 2k。现在，要读取一个数字的基数为 2k 的数字，您只需检查数字中大小为 k 的位块，这可以使用一些位移位和逻辑 AND 快速实现。即使您的数字存储为可变长度整数，这也可能很快，假设可变长度整数使用某种不错的二进制编码。
关于algorithm - 线性时间中的基数排序与将输入转换为适当的基数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/37262656/