我应该在基数排序中使用哪个基地？我该如何转换基地？

Question

如果我必须对基数为10的整数列表进行排序，首先我将这些整数转换为基数2，然后执行基数排序并最终将整数转换回基数10？

一般来说，你如何执行基数不同于列表中整数基数的基数排序？

Answer 1

一般来说，这取决于输入如何表示。

如果输入被表示为固定宽度的整数值，则可以很容易通过使用除法以及mod碱基之间进行转换。例如，您可以通过计算n % b来获取数字n的最后一个b位数字，并可以通过计算n/b（舍入）关闭该数字。

如果你的输入被表示为字符串，那么很难重新解释其他基地的字符。在不使用花哨的算法技术的情况下，通常可以通过将数字块视为单个数字来切换为基数的基数，其中数字代表基数。您也可以使用较小的基数，例如，取每个数字，分别用较小的基数重写这些数字，然后使用小于一位的基数排序。

如果你有兴趣使用真正重量级的理论技术，this paper demonstrates a way to encode numbers in any base in binary in a way that allows for constant-time random access of the digits with no loss in space。这当然比其他方法更先进，恒定的因素可能会在实践中造成这种效率低下，但它表明理论上可以使用任何你想要的基础。