ash*_*shu 5 sorting string algorithm
我有 n 个字符串，每个字符串的长度为 n。我希望按升序对它们进行排序。
我能想到的最好的算法是n^2 log n，也就是快速排序。（比较两个字符串需要 O(n) 时间）。挑战是在 O(n^2) 时间内完成。我该怎么做？
此外，不允许使用基数排序方法，因为您事先不知道字母表中的字母数量。
Aks*_*rma -1
解决所有情况的问题不可能比 O(N^2 Log N) 更好。但是，如果存在可以放松字符串比较的约束，则可以对其进行优化。
-如果字符串具有高重复率并且来自有限有序集。您可以使用计数排序的想法并使用映射来存储其计数。稍后，仅对映射键进行排序就足够了。O(NMLogM) 其中 M 是唯一字符串的数量。您甚至可以直接使用 TreeMap 来实现此目的。
-如果字符串不是随机的，而是某个超级字符串的后缀，则可以很好地完成 O(N Log^2N)。http://discuss.codechef.com/questions/21385/a-tutorial-on-suffix-arrays