algorithm - 按字典顺序对单词进行排序

Question

给定 n 个单词，是否可以以 o(n) 时间复杂度按字典顺序对它们进行排序？好吧，我发现了一种方法，例如创建 trie 数据结构和 trie 的中序遍历会导致时间复杂度接近 O(kn)，其中 k 是任意字符串长度，但这里的问题是空间复杂度。构造 BST 和中序遍历也是一个不错的选择，但时间复杂度为 O(nlogn) 。因此，鉴于两者的限制，谁能建议我哪个会更好 BST 或 trie。也欢迎任何其他算法或建议。

Answer 1

使用桶排序或基数排序很容易对单词进行O(nL)及时排序。这里是字长。不可能做得更好，因为您必须至少查看所有键一次。 L

你的三分法想法是一个古老的想法。