如果他们需要 O(n) 时间对列表进行排序，为什么我们不使用尝试进行排序？
Why don't we use tries for sorting if they take O(n) time to sort a list?
这里描述了使用 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) 的下限是 comparison sorts，即数组中的元素只能相互比较以检查一个应该在另一个之前还是之后，或者它们是否是平等的。这是 general 排序算法的一个很好的模型，因为它几乎适用于您可能想要排序的任何类型的数据；数字、字符串、用户定义的实例 类，等等。它甚至可以只是一种数据类型，可以通过 key 函数 映射到其他支持比较的数据类型；或者你可以接受一个比较器函数来进行比较。
请注意，这里的 O(n log n) 是比较次数的下限，而不是 运行 时间。如果每次比较花费的时间都超过 O(1)，比如因为您正在比较具有长公共前缀的长字符串，那么 运行 时间将类似于 O(cn log n)，其中比较在 O 中完成(三) 时间。例如，比较长度为 w 的字符串在最坏情况下需要 O(w) 时间。
如果您只需要针对特定类型数据的排序算法，那么您可能会做得更好，因为可以对元素执行特定于该数据类型的其他操作。例如，在对整数进行排序时，可以使用数组元素索引另一个数组，给出数组元素的counting sort algorithm which runs in O(n + r) time where r is the range。
如果排序键类似于字符串，在某种意义上它们是（或可以映射到）序列，因此比较键等同于 lexicographically comparing those sequences, then indeed you can use a trie to sort an array containing that data type. Congratulations: you have independently reinvented the radix sort algorithm, which can be implemented using tries。它的 运行 时间是 O(wn)，而不是 O(n)，因为将长度为 w 的字符串插入到 trie 中需要 O(w) 时间，而你必须这样做 n 次。
因此，如果元素不是字符串，或者上述意义上的 "string-like"，则基数排序根本不适用。如果元素是字符串或 "string-like"，则基数排序有效，但它需要 O(wn) 时间而不是 O(cn log n)。
这意味着基数排序并不是严格意义上的更好，而且当字符串的公共前缀相对于字符串本身较短时可能更糟，这种情况经常发生。对于随机字符串，常规字符串比较平均需要 O(1) 时间，在这种情况下，对于长于 O(log n) 的字符串，O(n log n) 渐近优于基数排序。
在实际应用中，还要考虑渐近分析中的隐常数。与遍历其节点在内存中不连续的树相比，比较排序 Timsort have low hidden constants because they access array elements sequentially, which results in fewer cache misses。
使用 trie 对字符串进行排序更快，但它需要构建一个 trie，这可能很昂贵。在许多情况下，使用比较排序更灵活，可以做到 in-place.
这里描述了使用 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) 的下限是 comparison sorts，即数组中的元素只能相互比较以检查一个应该在另一个之前还是之后，或者它们是否是平等的。这是 general 排序算法的一个很好的模型，因为它几乎适用于您可能想要排序的任何类型的数据；数字、字符串、用户定义的实例 类，等等。它甚至可以只是一种数据类型，可以通过 key 函数 映射到其他支持比较的数据类型；或者你可以接受一个比较器函数来进行比较。
请注意，这里的 O(n log n) 是比较次数的下限，而不是 运行 时间。如果每次比较花费的时间都超过 O(1)，比如因为您正在比较具有长公共前缀的长字符串，那么 运行 时间将类似于 O(cn log n)，其中比较在 O 中完成(三) 时间。例如，比较长度为 w 的字符串在最坏情况下需要 O(w) 时间。
如果您只需要针对特定类型数据的排序算法，那么您可能会做得更好，因为可以对元素执行特定于该数据类型的其他操作。例如，在对整数进行排序时，可以使用数组元素索引另一个数组，给出数组元素的counting sort algorithm which runs in O(n + r) time where r is the range。
如果排序键类似于字符串，在某种意义上它们是（或可以映射到）序列，因此比较键等同于 lexicographically comparing those sequences, then indeed you can use a trie to sort an array containing that data type. Congratulations: you have independently reinvented the radix sort algorithm, which can be implemented using tries。它的 运行 时间是 O(wn)，而不是 O(n)，因为将长度为 w 的字符串插入到 trie 中需要 O(w) 时间，而你必须这样做 n 次。
因此，如果元素不是字符串，或者上述意义上的 "string-like"，则基数排序根本不适用。如果元素是字符串或 "string-like"，则基数排序有效，但它需要 O(wn) 时间而不是 O(cn log n)。
这意味着基数排序并不是严格意义上的更好，而且当字符串的公共前缀相对于字符串本身较短时可能更糟，这种情况经常发生。对于随机字符串，常规字符串比较平均需要 O(1) 时间，在这种情况下，对于长于 O(log n) 的字符串，O(n log n) 渐近优于基数排序。
在实际应用中，还要考虑渐近分析中的隐常数。与遍历其节点在内存中不连续的树相比，比较排序 Timsort have low hidden constants because they access array elements sequentially, which results in fewer cache misses。
使用 trie 对字符串进行排序更快，但它需要构建一个 trie，这可能很昂贵。在许多情况下，使用比较排序更灵活，可以做到 in-place.