以下是使用trie:对字符串进行排序的算法的描述
该算法首先在O(n)时间插入trie中的所有项目，其中n是要排序的单词列表中的字符总数。
然后，它按顺序遍历树，当它到达设置了is_end标志的节点时，打印出一个前缀前面的节点。这需要对trie进行完全遍历，这需要O(m)时间，其中m是trie中的节点数。这是受n约束的，所以这一步也受O(n)约束。
整个算法由两个子例程组成，每个子例程以O(n)为界。例如，如果我们说平均单词包含c个字符，那么如果m是单词的数量cm == n，并且总运行时间以O(n) == O(cm) == O(m)为界(我将其更改为m的原因是因为这是要排序的列表长度的传统度量，而不是字符总数(。
因此，我的问题是，如果这个运行时分析是正确的，为什么这不是字符串排序的默认方法，因为它比任何O(nlogn)排序算法都快？
O(n log n(下界用于比较排序，即数组中的元素只能相互比较，以检查一个元素是在另一个元素之前还是之后，或者它们是否相等。对于通用排序算法来说，这是一个很好的模型，因为它适用于您可能想要排序的几乎任何类型的数据；数字、字符串、用户定义类的实例等等。它甚至可以只是一种数据类型，可以通过键函数映射到其他支持比较的数据类型；或者您可以接受比较器函数来进行比较。
请注意，这里的O(n&log-n(是比较次数的下限，而不是运行时间。如果每次比较花费的时间超过O(1(，比如说，因为您正在比较具有长公共前缀的长字符串，那么运行时间将类似于O(cn；log；n(，其中比较是在O(c(时间内完成的。例如，在最坏的情况下，比较长度为w的字符串需要O(w(时间。
如果您只需要对特定类型的数据使用排序算法，那么您可能会做得更好，因为可以对元素执行特定于该数据类型的其他操作。例如，在对整数进行排序时，可以使用数组元素对另一个数组进行索引，给出在O(n+r(时间内运行的计数排序算法，其中r是数组元素的范围。
如果排序键像字符串，从某种意义上说，它们是(或可以映射到(序列，因此比较键相当于字典式地比较这些序列，那么实际上，您可以使用trie对包含该数据类型的数组进行排序。祝贺你：你已经独立地重新发明了基数排序算法，它可以通过尝试来实现。它的运行时间是O(wn(，而不是O(n(，因为将长度为w的字符串插入trie需要O(w(时间，并且必须执行n次。
因此，如果元素不是字符串，或者不是上述意义上的"类似字符串"，则基数排序根本不适用。如果元素是字符串或"类似字符串"，则基数排序有效，但它需要O(wn(时间，而不是O(cn&log ；n(。
这意味着基数排序并不是严格意义上的更好，当字符串的公共前缀相对于字符串本身较短时，情况可能会更糟，通常就是这种情况。对于随机字符串，常规字符串比较平均需要O(1(时间，在这种情况下，对于长于O(log-n(的字符串，O(n&log-n(渐近地优于基数排序。
在实际应用中，还应考虑渐近分析中的隐藏常数。Timsort这样的比较排序具有较低的隐藏常数，因为它们按顺序访问数组元素，与遍历节点在内存中不连续的树相比，这会减少缓存未命中。
对字符串进行尝试排序更快，但它需要构建一个trie，这可能很昂贵。在许多情况下，使用比较排序更灵活，并且可以就地执行。