algorithm - 编写一个方法来对两个不同字符串的字符进行排序，而不是对这些字符串的数组进行排序？

Question

基本思想是对字符串进行排序并比较字符串的签名，其中签名是按字母顺序排序的字符串。

这样做的有效算法是什么？

Answer 1

如果您要“按字母顺序”对 UTF8 字符进行排序，则可以将它们转换为 32 位整数(UTF8 字符是 1 到 4 个 8 位值)，然后执行 RADIX sort .它将在 O(N) 时间内工作。如果你只使用 ASCII，我会建议 Counting Sort .

有很多方法可以匹配签名，但我会使用 Hash Table (平均 O(1) )或 O(Lg N) 结构，例如 Red-Black Trees或 Skip-Lists .

为了进一步加快您的字符串匹配，您可以通过 Run Length Encoding 压缩这些签名这些 UTF8 字符(因为它们已排序，签名将是运行 + 间隙)。实际上，您可以压缩它们以使用位标记来表示 7 位字符(最常见)、RLE 运行和更长的文字(8 位到 32 位字符)。比较压缩字符串会更快。