c# - 任意长度字符串的基数排序

Question

我需要对大量任意长度的文本字符串进行排序。我想基数排序是最好的选择。 List 实在是太大了，所以填充相同长度的字符串是完全不可能的。
这个任务是否有任何现成的实现，最好是在 C# 中？

Answer 1

根据您的需要，您可能会发现将所有字符串插入某种形式的 Trie 中是最佳解决方案。即使是基本的三元搜索树也比字符串数组/列表占用更少的内存，并且会按排序顺序存储字符串。

插入、查找和删除都是 O(k * log(a)) 其中 a 是字母表的大小(一个字符的可能值的数量).由于 a 是常量，log(a) 也是常量，所以您最终得到一个用于排序的 O(n * k) 算法。

编辑:如果您不熟悉 Tries，它们基本上是 n 元树，其中每条边代表键的单个字符。插入时，您检查根节点是否包含与键的第一个字符匹配的边(或子节点，等等)。如果是，则按照该路径重复第二个字符，依此类推。如果不是，则添加一条新边。在三元搜索树中，边/子节点存储在二叉树中，因此字符按排序顺序排列，可以在 log(a) 时间内搜索。如果你想浪费内存，你可以将边缘/ child 存储在一个大小为 a 的数组中，这样你就可以在每一步不断查找。