使用合并排序的字符串排序

使用合并排序的字符串排序

与@orangeoctopus一样，

n

对大小字符串的集合使用标准排名算法

n

将导致

O(n^2 * logn)

计算。

然而-注意，你 可以
做到这一点的

O(n^2)

，对变异基数排序。

[我认为]最简单的方法是

1. 构建一个trie，并用所有字符串填充它。输入的每个字符串是

   O(n)

   ，您输入的

   n

   时间为-总计

   O(n^2)

2. 每次遇到字符串结尾标记时，请在trie上执行DFS-将其添加到排序的集合中。以这种方式添加的字符串的顺序按字典顺序排列，因此完成后，将按字典顺序对列表进行排序。

很容易看到您不能再做得更好

O(n^2)

，因为只能读取数据

O(n^2)

，因此从时间复杂度的大O标记来看，此解决方案是最佳的。