如果我必须对以 10 为底的整数列表进行排序，首先我将此整数转换为例如以 2 为底的整数，然后执行基数排序，最后将整数转换回以 10 为底的整数？
一般来说，如何使用不同于列表中整数基数的基数执行基数排序？
问问题
568 次
1 回答
0
一般来说，这取决于输入的表示方式。
如果您的输入表示为固定宽度的整数值，那么使用除法和 mod 在基数之间进行转换很容易。例如，您可以通过计算获得数字 n 的最后一个 base-b 数字，并且可以通过计算（向下舍入）n % b删除该数字。n / b
如果您的输入表示为字符串，则很难重新解释其他基础中的字符。在不使用花哨的算法技术的情况下，您通常可以切换到作为基数的基数的基数，通过将数字块视为单个数字来表示数字。您还可以使用较小的基数，例如，取每个数字，在较小的基数中单独重写这些数字，然后使用一次少于一个数字的基数排序。
如果您对使用真正重量级的理论技术感兴趣，本文演示了一种以二进制形式对任何基数的数字进行编码的方法，该方法允许对数字进行恒定时间随机访问而不会丢失空间。这肯定比其他方法更先进，并且常数因素可能会使这种方法在实践中效率低下，但它表明理论上可以使用您想要的任何基础。
于 2015-08-26T20:55:09.710 回答