5

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

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

4

5 回答 5

8

您可以将所有单词放在trie（或radix tree）中，然后按DFS顺序打印，从 DFS 中每个级别的“较小”词典字母开始。

该解决方案将是平均字符串长度在O(n* |S|)哪里。|S|

简单的例子：

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

结果尝试将是：

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

还有一个 DFS（它更喜欢字典上较小的字符）：DFS 将从 开始a，转到b，然后到结束符号 ( $) 并且将首先打印ab，然后返回到a，然后返回到 ，c然后到下一个$符号，并且将print ac, and next to aand its $and will print aca，导致打印：

ab
ac
aca

如前所述。

于 2012-10-28T14:59:31.277 回答
1

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

归并排序和堆排序的最坏情况运行时间都是 O(nlog(n))... 快速排序的最坏情况运行时间是 O(n^2)，但平均运行时间是 O(n^日志（n））。

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

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

MSD 基数排序可以使用数字（在本例中为字符）的字典顺序并从左到右对字符串进行排序。

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

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

于 2012-10-28T15:18:43.647 回答
1

好吧，我已经阅读（并赞成）关于基数排序和基数特里的答案，非常有用。
但。
在基数排序的情况下 - 您需要对 N 元素进行 91 次传递，因此它将是91 * N。我不是在谈论额外的空间。
在合并排序的情况下，您有N * log N比较，并且由于 log N = log 1000000 ~ 20 您有20 * N比较。

那么哪个更快呢？:) 或者我可能在某个地方弄错了？

于 2012-10-28T16:15:23.330 回答
0

可以计算 ascii 值，因此本质上这是一个整数排序。基于比较的排序例程充其量只会为您提供 O(n lg n) - 合并排序（需要额外的空间来创建另外两个大小为 n/2 的数组）或在最坏的情况下为 O(n^2)（插入排序、快速排序，但它们没有额外的空间复杂度）。这些比线性排序算法渐近地慢。我建议查看 CLRS（http://www.amazon.com/Introduction-Algorithms-Thomas-H-Cormen/dp/0262033844）。关于线性时间排序的章节。在这种情况下，O(n) 可能是您可以做的最好的事情。此外，这篇文章可能会有所帮助。线性时间排序？

我会检查基数排序。http://en.wikipedia.org/wiki/Radix_sort

于 2012-10-28T15:04:35.613 回答
0

为什么不按三个字符进行分布排序：那将需要 19683 (27*27*27) 个元素的计数存储，这应该是可行的，然后最多需要 34 遍。

但是很快，每个键的子列表（三个字符的倍数）将足够短，可以对字符串的其余部分使用插入排序或类似的方法。1.000.000/(27^3) 约为 50

如果它们具有共同的长前缀，则相同的机制可以用于更长的键，即前 30 个字符会将列表划分为仅 20 或 30 个子列表。然后，您不会将键表示为数字，而是表示为字符串，并将它们存储在字典中，这样速度较慢，但​​所需的传递次数更少，内存也可能更少。此外，它还需要 N*log(M) 查找，其中 M 是二叉树中不同键的数量，但散列也是一种可能。

于 2013-05-14T14:53:27.827 回答