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

Question

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

Answer 1

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

你的 triesort想法是一个古老的想法。