sorting - 设A为n个正整数的数组，已知数组中的最大数为k=n^5。找到可能的最佳排序

Question

我在测验中得到了下一个问题：

设A为n个正整数的数组，已知数组中的最大数为k=n^5。找到算法的最佳可能排序。

我的回答是：因为我知道最大的数字（以及它的位数），首先我会找到它的位数，然后我会使用基数排序。

官方给出的答案是：基数排序，以n为基数，d=6。

我不明白为什么？为什么d=6？为什么选择 n 作为基础？谢谢。'

Answer 1

因为 n^5 是 1，后跟以 n 为底的 5 个零：

• 如果 n=10，则 10^5 = 10000。
• 如果 n=2，则 2^5 = 32 = 10000 二进制。