字符串相等长度的 C++ 排序算法

Question

我需要按ASCII码顺序和长度对大约10万个字符串进行排序。我通过将其放入长度为字符串长度的2D向量中，然后使用快速排序算法（按ASCIIbetically）对每个数组进行排序来实现按长度排序。但是，有没有更快的方法可以对相等长度的字符串进行排序？我听说基数排序很好，但我发现它很难理解。如果不使用sort()函数，最好的方法是什么？如果你需要代码，我可以贴出来。

- Jackson Collins

---

按ASCII字母顺序排序 - 不错的一个 :-) - paxdiablo

这是一件事情，我发誓 =] - Jackson Collins

好的，我们有大约 100000 个字符串，并且我们需要以最快的方式将这些字符串排序 n 次。例如，“the piece of puzzle Was higher” 将变成“of Was the piece higher puzzle”。我只是在寻找一种更快的方法来按这种方式排序字符串。 - Jackson Collins

你使用的是哪种编程语言？你能在排序函数中插入自定义比较器吗？ - Henry

你读过这篇文章吗：为字符串工程化基数排序？它花了很多心思来优化字符串的基数排序。 - vgru

Answer 1

我认为构建一个Trie树，并通过先序遍历来检索Trie树中的键，是字符串排序最有效的方法之一，实际上是基数排序的一种形式。 这里有一篇详细的学术论文讨论了这种方法。至少在2006年，这是当时最快的字符串排序方法。

- WeaselFox

---

目前我使用向量和快速排序算法对大约70000个字符串进行排序，耗时约为0.38秒。使用字典树能否更快呢？（当然这也取决于计算机的性能） - Jackson Collins

抱歉，多了一个数字0.38秒。 - Jackson Collins

有没有人有一些关于 trie 的简单示例代码，我可以查看一下，甚至是伪代码？ - Jackson Collins

Answer 2

对于长度在8到15个字符之间的字符串，您的快速排序比较函数可以在单个64位块中处理前8个字符。对于16到31个字符等等，以此类推。因此，您最终会得到尽可能多的比较函数。除非您有大量具有长公共子字符串的字符串，否则仅使用有关字符串长度的已知信息可能会直截了当地解决问题。

为了完整起见，您需要考虑对齐和字节顺序。因此，将每次提取8个字节到一个uint64_t中：

  uint64_t u ;

  memcpy(&u, pv, 8) ;
  ...convert to big-endian if required...

我可以告诉你，在x86_64上，使用gcc和-O2编译时，memcpy()编译成一条指令，就像是u = *(uint64_t*)pv一样。对于存在对齐问题的处理器，我希望编译器能够做出适当的处理。

遗憾的是，memcmp(foo, bar, 8)没有得到相同的待遇（至少在gcc 4.8上，即使使用-O3）:-(

- user3793679