algorithm - 对仅包含 a-z 和空格的单词数组进行排序的最快方法是什么？

Question

我想知道是否有比快速排序/合并排序更快的方法对此类数组进行排序。

数组的最大长度为 10^6。单词的长度 >=10 且 <= 100，单词可以包含 a-z 和空格(总共 27 个不同的字符)。单词中的字符不是唯一的(它们可以重复)。数组中的所有单词都等长。

Answer 1

你可以把所有的词都放在一个 trie 中(或 radix tree )，然后将其打印在 DFS 中顺序，从 DFS 中每个级别的“较小”词典字母开始。

此解决方案将是 O(n* |S|)，其中 |S| 是平均字符串长度。

简单的例子:

设字符串集为[ac,ab,aca]:

生成的 trie 将是:

         a
       /  \
      /    \
     b      c
     |     / \
     $    $   a
              |
              $

还有一个 DFS(它更喜欢按字典顺序排列的较小字符):DFS 将从 a 开始，转到 b，然后到结束符号 ($ ) 并且会先打印ab，然后返回到a，然后右转到c，再到下一个 $ 符号，将打印 ac，并在 a 及其 $ 旁边打印 aca，导致打印:

ab
ac
aca

如前所述。