如何最快地对只包含a-z和空格的单词数组进行排序？

Question

我想知道是否有比快速排序/归并排序更快的方式来对这样的数组进行排序。

最大数组长度为10^6。 单词长度大于等于10且小于等于100，单词中可以包含a-z和空格（总共27个不同的字符）。 单词中的字符不一定唯一（可以重复出现）。 数组中的所有单词长度都相等。

- Patryk

---

如果您没有有关传入数据可能顺序的信息，那么就没有“最快”的方法。您必须根据最佳情况与最坏情况的性能（以及每种情况的可能性）以及存储/数据访问限制之一选择流行算法。 - Hot Licks

整个数组都能放入内存中吗？ - goat

Answer 1

你可以把所有的单词放在一个trie（字典树）（或基数树(radix tree)）中，然后从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

如预期。

- amit

---

但是基数树是实现起来比较复杂的算法之一，而存储管理的成本很容易超过所谓的O效率的增益。 - Hot Licks

Answer 2

任何基于比较的排序算法的下限都是O(nlog(n))。你不能有任何基于元素相互比较的排序算法，其最坏情况运行时间低于此限制。

归并排序和堆排序的最坏情况运行时间均为O(nlog(n))... 而快速排序的最坏情况运行时间为O(n^2)，但平均运行时间为O(n^log(n))。

值得一提的是，尽管快速排序的最坏运行时间为O(N^2)，但由于具有小的常数因子和适合当前机器架构的高效执行能力，它有时会击败其他O(nlog(n))运行时间的算法（如堆排序）。

线性排序算法允许在非比较基础上以O(n)的线性时间对整数进行排序（但不仅限于整数）（例如：计数排序、桶排序和基数排序）

MSD基数排序可以使用数字（在这种情况下是字符）的字典顺序从左到右对字符串进行排序。

它首先使用另一个线性排序算法（例如桶排序）根据最左边的字符对所有字符串进行排序，然后再次使用左起第二个字符进行排序，直到按最右边的字符排序。最终，数组将完全排序。

该算法的运行时间为O(k*N)，其中N是元素数量，k是平均键长（在这种情况下，它将是>=10 && <=100的单词长度）。

- Moustafa Alzantot

Answer 3

我已经阅读（并点赞）了关于基数排序和基数树的答案，非常有启发性。
但是。
在基数排序的情况下 - 您需要进行91次N元素的排序，因此它将是91 * N。 我不是在谈论额外的空间。
在归并排序的情况下，您有N * log N次比较，由于log N = log 1000000 ~ 20，因此您得到20 * N次比较。

那么哪个更快呢？ :) 或者我可能犯了什么错误吗？

- Roman Pekar

---

但是归并排序在每次迭代中需要读取整个字符串（最坏情况下，除非您可以提供更好的分析），而在基数排序中，每个比较都是在字符串中的单个字符上进行的，因此尽管您有更多的比较操作，但每个操作的成本显着降低，因为它不需要读取整个字符串。[附言：感谢您的点赞 :) ] - amit

你说得对，归并排序进行比较，基数排序只是简单地通过。这很琐碎，感谢你指出来。归并排序肯定比在每次迭代中读取整个字符串要好一点，但我不认为它会帮助超过基数排序。 - Roman Pekar

Answer 4

为什么不按每三个字符进行分布排序：这将需要一个包含19683（27*27*27）个元素的计数存储器，这应该是可行的，然后最多需要34次操作。

但很快，每个键（三个字符的倍数）的子列表将变得足够短，可以在字符串的剩余部分上使用插入排序或类似方法。1000000 /（27 ^ 3）约为50

如果长键具有共同的长前缀，例如前30个字符将只将列表分成20或30个子列表，则可以使用相同的机制。然后，您不将键表示为数字，而是将它们作为字符串存储在字典中，这会更慢，但需要的操作次数更少，可能也需要更少的内存。此外，它将需要大约N * log（M）次查找，其中M是二叉树中不同键的数量，但哈希也是一种可能性。

- Jan Boonen

Answer 5

ASCII值可以计算，因此这是一个整数排序。基于比较的排序例程最多只能获得O(n lg n) - 归并排序（需要额外的空间来创建两个大小为n/2的数组）或者最坏情况下的O(n^2)（插入排序，快速排序，但它们没有额外的空间复杂度）。这些算法在渐近意义下比线性排序算法慢。我建议看一下CLRS（http://www.amazon.com/Introduction-Algorithms-Thomas-H-Cormen/dp/0262033844）。其中有关于线性时间排序的章节。在这种情况下，O(n)可能是最好的选择。此外，这篇文章可能会有所帮助。Sorting in linear time?

我建议查看基数排序。http://en.wikipedia.org/wiki/Radix_sort

- The Internet