对O（n）中的数组进行排序

Question

假设您有n个整数，范围从0到n^3-1。有没有什么办法可以在O（n）时间对它们进行分类？我得到了Uni的这个问题，据我所知，只能使用mergesort或quicksort在NlogN中搜索它们，所以我怀疑这是一个诡计的问题。我还想知道为什么给出了（0，n^3-1）的特定范围？它有什么特别的特征吗？我也在考虑使用Counting Sort来做它们，但据我所知，它运行在O（n + k）时间内，而不是O（n）。请帮忙！

Answer 1

使用“计数排序”，您可以在O（n）中的最后n位以稳定的方式对项进行排序。然后你可以在中间位上排序，然后在最高位上排序。因为密钥小于n^3 - 1，所以计数排序的数量是固定的（三个），而O（n）的三倍仍然是O（n）。