如何快速地对n个长度为n的字符串进行排序？

Question

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

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

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

- piedpiper

---

没有明确的限制，所以我认为我们可以假设10^4或更大。 - piedpiper

好的，您可以遍历字符串中的N^2个字母来计算字母表中的字母数量（仅需要O(N^2)时间），然后使用基数排序... - T.C.

我们可以将其视为Unicode，共65536个字符。 - piedpiper

@T.C. 感谢您的回复。然而，这个解决方案在最坏情况下仍不是O(n^2)。您有什么见解吗？ - piedpiper

我无法将Unicode视为65536个字符。这是一个非常奇怪的数字；BMP具有较少的字符，但整个字符集却更多；代码点不在连续块中；代理对需要成对出现；...??? - Tom Blodget

Answer 1

假设任何字母都是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

注意：字母收集的假设决定了排序数组的长度。

- Danyu

---

"zdcbacdca"只是一个字符串，我认为你误解了问题。 - Pham Trung

你想按升序对所有字符串进行排序吗？！ - Danyu

所以，举个例子，我们有一个输入是zzz、abc、bcd、acd，对吧？期望的输出是abc、acd、bcd、zzz :) - Pham Trung

Answer 2

你可以构建一个Trie，它的时间复杂度为O(s*n)。

Details: https://dev59.com/c2rWa4cB1Zd3GeqP7ylV#13109908

- Sazzad Hissain Khan

Answer 3

对于少量字符串，常规比较排序可能比基数排序更快，因为基数排序需要的时间与存储每个字符所需的位数成正比。对于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]用于X和LCPY[0]，...，LCPY[k-1]用于Y），我们也需要生成LCPZ[0]，...，LCPZ[2k-1]。 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]]小，则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 值很容易：如果最后两个失败者都来自 X，则取 LCPX[i]；如果它们都来自 Y，则取 LCPY[j]；如果它们来自不同的块，则取 L 的上一个值。

实际上，我们可以做得更好。假设最后一次比较发现S[X [i]] < S[Y [j]]，因此X [i]是最近追加到Z的字符串索引。 如果M（= LCPX [i + 1]> L），则我们已经知道S[X[i+1]] < S[Y[j]]甚至不需要进行任何比较！这是因为要达到当前状态，我们知道S[X[i]]和S[Y[j]]必须首先在字符位置L处有所不同，并且在S[X[i]]中该位置上的字符x小于S[Y[j]]中该位置上的字符y，因为我们得出结论S[X[i]] < S[Y[j]]--因此，如果S[X[i+1]]与S[X[i]]共享至少前L+1个字符，则它也必须包含S[X[i]]位置L上的x，因此它也必须比S[Y[j]]小进行比较。（当然情况是对称的：如果最后一次比较发现S[Y[j]]

我不知道这是否会将复杂度从O(n^2logn)提高到更好的级别，但这应该会有所帮助。

- j_random_hacker

Answer 4

在比O(N^2LogN)更好的时间复杂度内解决所有情况似乎不可能。 但是，如果有可以放宽字符串比较的约束条件，可以进行优化。

- 如果字符串具有高重复率并来自有限有序集合，可以借鉴计数排序的思想，并使用映射存储它们的计数。随后，仅对映射键进行排序即可。时间复杂度为O(NMLogM)，其中M是唯一字符串的数量。甚至可以直接使用TreeMap实现此目的。

- 如果字符串不是随机的，而是某个超级字符串的后缀，则可以很好地完成这项工作。时间复杂度为O(NLog^2N)。http://discuss.codechef.com/questions/21385/a-tutorial-on-suffix-arrays

- Akshay Sharma