C中基数排序的不同基数

Question

我很难理解基数排序。我没有问题实现代码使用2或10的基数。但是，我有一个分配，需要命令行参数来指定基数。基数可以是2到100,000。我花了大约10个小时试图理解这个问题。我不是要求直接回答，因为这是作业。但是，如果有人能对此有所了解，请做。

我不明白的一些事情。拥有100,000的基础有什么意义？怎么会这样呢？我理解为每个字母表中的字母或每个数字1-9都有一个基数。我似乎无法绕过这个概念。

如果我不够具体，我很抱歉。

Answer 1

任何基数B中的数字N只是[0，B-1]范围内的一系列数字。由于我们没有足够的符号来表示“普通”人类书写系统中的所有数字，所以不要考虑它是如何用字符书写的。您只需要知道数字是分开存储/写入的

例如，基础177中的255是2位数字，其中第一个数字具有值1，第二个数字具有值78，因为25510 = 1×1771 + 78×1770。如果某些文化使用这个基础，它们将有数字的177个不同符号，并且它们只用2位数字写入。由于我们只有10个符号，我们需要定义一些符号来分隔数字，这通常是:。从Wolfram Alpha，255₁₀ = 1:78₁₇₇可以看到

请注意，并非所有人都计入基数10.存在cultures that count in base 4, 5, 6, 8, 12, 15, 16, 20, 24, 27, 32, 36, 60 ...因此他们将拥有比我们大多数人更多或更少的符号。然而，在非小数基数中，现在只有基数20,12和60是最常用的。

在基数100000中它是相同的。 1234567890987654321将是一个4位数字，写为符号，值为1234,56789,9876,54321

Answer 2

我准备在评论中解释它，但基本上你在谈论我们有时称之为“模运算”。每个数字是{0 ... n-1}并且表示n ^ k的时间，其中k是位置。十进制255是5 * 10 ^ 0 + 5 * 10 ^ 1 + 2 * 10 ^ 2。

所以，你的255基础177很难表示，但在177s位置（177 * 10 ^ 1）有1，在1s（177 * 10 ^ 0）位置有78。

作为一般的伪代码算法，你想要像...

n = input value
digits = []
while n > 1
    quotient = n / base (as an integer)
    digits += quotient
    remainder = n - quotient * base
    n = remainder

你可能需要检查最后的剩余部分，以防出现问题。

当然，你如何表示这些数字是另一回事。例如，MIME包含通过Base-64处理的半标准方式。

如果是我，我只是分隔数字并清楚表明它是表示，但是如果你想要使用类似十六进制的扩展，那就是全部的Unicode ...