相关疑难解决方法(0)

给定[0..n ^ 3-1]范围内的n个整数的输入集,提供线性时间排序算法.

这是我星期四测试的评论,我不知道如何解决这个问题.

我有 n 个字符串，每个字符串的长度为 n。我希望按升序对它们进行排序。

我能想到的最好的算法是n^2 log n，也就是快速排序。（比较两个字符串需要 O(n) 时间）。挑战是在 O(n^2) 时间内完成。我该怎么做？

此外，不允许使用基数排序方法，因为您事先不知道字母表中的字母数量。