设A是n个正整数的数组，已知数组中的最高数是k = n^5。找到最好的排序

让A为n个正整数的数组，已知数组中的最高数为k = n^5。找出算法的最佳排序。

我的答案是：因为我知道最高的数字（和其数字的数量），首先我会找到它的数字量，然后我将使用基数排序。

官方回答是：基数排序，以n为基数，d = 6。

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

我认为这个问题/官方答案有些不妥。这取决于你的意思是什么“尽可能好”，但是对于小巧的我会期望像quicksort这样简单的排序方法会击败基数排序。对于大的n，它将取决于数据的分布：如果它已经接近排序，那么timsort可能会赢，例如... – mikera

官方答案完全忽略了基本转换可能是昂贵的操作或使用实际电脑通常最好坚持原生支持的基础（即2 ** 8,2 ** 16,2 ** 32或2 ** 64）。 – salva

由于N R个5之后是1由5个零在基数n：

2013-07-04 08:54:00 Tordek

它如何适合基数排序？我的意思是，让我们取n = 2，Array [11,31]。就像我看到的那样，基数排序通过最低有效位数，根据给定的基数对它进行排序，对于11和31我都应该得到相同的结果[1为LSD，1为后面的]或者我只是不了解基数排序。 – StationaryTraveller

你在基数n上进行基数排序，所以如果n = 1，你的数组是[01011,01111]，并且你通过对每一位进行排序来执行基数排序。（也就是说，对于第一步，两个位置均为0;对于第二步，两者都为1;对于第三步，11具有0但31具有1;以此类推）。 – Tordek

回答