对仅包含a-z和空格的单词数组进行排序的最快方法是什么？ [英] What would be the fastest way to sort an array of words containing a-z and spaces only?

问题描述

我想知道是否有比快速排序/合并排序更快的方法来排序这种数组。

I'd like to know if there's some faster way to sort such array than quicksort/mergesort.

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

Maximum array's length is 10^6. Word's length is >=10 and <= 100 and the word can contain a-z and spaces (27 different characters in total). Characters are not unique in the words (they can repeat). All the words in an array are equally long.

推荐答案

您可以将所有单词放在 trie （或基数树），然后将其打印到 DFS 顺序，从DFS中每个级别的较小字典字母开始。

You can put all the words in a trie (or a radix tree), and then print it in a DFS order, starting from the "smaller" lexicographical letter at each level in the DFS.

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

This solution will be O(n* |S|) where |S| is the average string length.

简单例如：

让字符串集为 [ac，ab，aca] ：

结果特里将是：

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

和一个DFS（首选按字典顺序较小的字符）：DFS从 a ，转到 b ，然后到结束符号（ $ ），将首先打印 ab ，然后返回 a ，然后右移至 c ，并显示到下一个 $ 标记，并显示 ac ，然后显示下一个到 a 及其 $ 并打印 aca 打印中：

And a DFS (which prefers lexicographically smaller characters): The DFS will start from a, go to b, and then to the end sign ($) and will first print ab, then go back to a, and right to c, and to the next $ sign, and will print ac, and next to a and its $ and will print aca, resulting in printing:

ab
ac
aca

扩展。

这篇关于对仅包含a-z和空格的单词数组进行排序的最快方法是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！