对包含az和空格的单词数组进行排序的最快方法是什么？

Question

我想知道是否有一些比quicksort/mergesort更快的方式来排序这样的数组.

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

Answer 1

您可以将所有单词放在trie(或基数树)中,然后以DFS顺序打印它,从DFS中每个级别的"较小"词典字母开始.

该解决方案将是O(n* |S|),其中|S|是平均字符串长度.

简单的例子:

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

由此产生的特里将是:

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

还有一个DFS(它更喜欢字典上较小的字符):DFS将从,开始a,b然后到结束符号($)开始ab,然后首先打印,然后返回到a右边c,再到下一个$标志,并且打印ac,而旁边a和它$会打印aca,从而导致打印:

ab
ac
aca

被驱逐出境.