为什么对字符串进行排序是 O(n log n)？ [重复]

Question

可能重复：
大O的通俗英语解释

在编程难题的答案中，它说

sorting a string takes  O(n log n) time

。 是怎么推导出来的？

有人有 Big O 资源的良好参考链接吗？

Answer 1

为什么对字符串进行排序是 O(n log n)？

对字符串中的字符进行排序不一定是 O(n log n)。

• O(n log n) 是比较排序的最佳值。这也是许多语言默认排序实现的复杂性。然而，当然有可能做得比这更糟糕。对字符串中的字符进行排序的复杂性取决于您选择解决此任务的特定算法。
• 在某些情况下，通过使用非比较排序的排序算法也可能比 O(n log n) 做得更好。例如，如果您知道自己的 ASCII 字符串最多包含 127 个不同字符，则可以使用计数排序，其时间复杂度为 O(n)。对于 Unicode 字符串，计数排序也是可行的，其中所有字符都位于 Basic Multilingual Plane。

Answer 2

Big O 的定义和一些例子可以通过搜索引擎找到，例如这里：

• http://en.wikipedia.org/wiki/Big_O_notation

可以在此处找到基于比较元素的排序算法的说明，以及所需比较次数下限的说明：

• http://en.wikipedia.org/wiki/Comparison_sort