我有n个字符串，每个长度为n。我希望按升序对它们进行排序。
我能想到的最好的算法是n^2 log n，这是快速排序。(比较两个字符串需要O(n)时间)。难点在于要在O(n^2)的时间内完成。我该怎么做呢?
同样，基数排序方法是不允许的，因为你事先不知道字母表中的字母数。
假设任意字母从a到z
由于不需要就地排序，所以创建一个长度为26的链表数组:
List[] sorted= new List[26]; // here each element is a list, where you can append
对于该字符串中的一个字母，其排序位置是ascii: x-'a'的差值。例如，'c'的位置是2，它将被放在
的位置。sorted[2].add('c')
这样，排序一个字符串只取n。
所以对所有字符串排序需要n^2
例如，如果你有"zdcbacdca".
z goes to sorted['z'-'a'].add('z'),
d goes to sorted['d'-'a'].add('d'),
....
排序后，一个可能的结果看起来像
0 1 2 3 ... 25 <br/>
a b c d ... z <br/>
a b c <br/>
c
注意:字母收集的假设决定了排序数组的长度
对于少量字符串，常规比较排序可能比基数排序更快，因为基数排序所需的时间与存储每个字符所需的位数成正比。对于2字节的Unicode编码，并对相等常数因子进行一些(无可否认是可疑的)假设，基数排序只有在log2(n)> 16时才会更快，即排序超过约65,000个字符串时。
我还没有看到的一件事是，字符串的比较类型可以通过利用已知的公共前缀来增强。
假设我们的字符串是S[0]， S[1]，…S (n - 1)。让我们考虑使用最长公共前缀(LCP)表来扩展合并排序。首先，不是在内存中移动整个字符串，而是将索引列表操作到一个固定的字符串表中。
当我们合并两个字符串索引为X[0]的有序列表时，…， X[k-1]， Y[0]，…， Y[k-1]产生Z[0]，…， Z[2k-1]，我们也将得到2个LCP表(LCPX[0]，…， LCPX[k-1] for X, LCPY[0]，…， LCPZ[k-1]表示Y)，我们需要生成LCPZ[0]，…， LCPZ[2k-1] too。LCPX[i]给出了X[i]的最长前缀的长度，该前缀也是X[i-1]的前缀，LCPY和LCPZ也是如此。
S[X[0]]和S[Y[0]]之间的第一个比较不能使用LCP信息，我们需要完整的O(n)个字符比较来确定结果。但在那之后，事情就加速了。
在第一次比较中，在S[X[0]]和S[Y[0]]之间，我们还可以计算它们的LCP的长度——称之为l。设Z[0]为S[X[0]]和S[Y[0]]中比较小的一个，并设LCPZ[0] = 0。我们将在L中保存最近一次比较的LCP的长度。我们还将在M中记录最后一个"比较失败者"与其块中的下一个字符串共享的LCP的长度:也就是说，如果两个字符串S[X[i]]和S[Y[j]]之间最近的比较确定S[X[i]]更小，则M = LCPX[i+1]，否则M = LCPY[j+1]。
基本思想是:在任何合并步骤中的第一个字符串比较之后， S[X[i]]和S[Y[j]]之间的每个剩余字符串比较都可以从L和M的最小值开始，而不是从0开始。这是因为我们知道S[X[i]]和S[Y[j]]在开始时必须至少在这么多字符上一致，所以我们不需要比较它们。当形成越来越大的排序字符串块时，块中的相邻字符串将倾向于以更长的公共前缀开始，因此这些LCP值将变得更大，从而消除越来越多无意义的字符比较。
每次S[X[i]]和S[Y[j]]比较后，"失败者"的字符串索引照例追加到Z后面。计算相应的LCPZ值很容易:如果最后2个输家都来自X，取LCPX[i];若都是从Y来的，就取LCPY[j];如果它们来自不同的块，则取l的前一个值
事实上，我们可以做得更好。假设最后的比较发现S[X[i]] <如果M> L，那么我们已经知道S[X[i+1]] <S[Y]><S[Y[j]]——如果S[X[i+1]]与S[X[i]]至少共享第一个L+1字符，那么它也必须在位置L上包含X，因此它也必须小于S[Y[j]]。(当然，这种情况是对称的:如果最后的比较发现S[Y[j]]><S[X[i]]，只是交换名称。>
我不知道这是否会将复杂度从O(n^2 log n)提高到更好的程度，但它应该有所帮助。
您可以构建一个Trie，它将花费O(s*n)，
细节:https://stackoverflow.com/a/13109908
解出所有情况不可能比O(N^2 Log N)更好。但是，如果存在可以放松字符串比较的约束，则可以对其进行优化。
-如果字符串具有高重复率并且来自有限有序集。您可以使用计数排序中的概念，并使用映射来存储计数。稍后，仅对映射键进行排序就足够了。O(NMLogM)其中M是唯一字符串的个数。您甚至可以直接使用TreeMap来实现此目的。
-如果字符串不是随机的，而是一些超级字符串的后缀，这可以很好地完成日志O (N ^ 2 N)。http://discuss.codechef.com/questions/21385/a-tutorial-on-suffix-arrays