爲什麼排序字符串O（n log n）？

Question

可能重複：
Plain English explanation of Big O

在回答一個編程的難題故稱排序字符串需要爲O（n log n）的時間。 這是如何派生的？

有沒有人有一個很好的大O資源的參考鏈接。

由於

Answer 1

的定義和大O的一些例子可以通過使用搜索引擎中找到，例如這裏：

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

的基於比較元件排序算法的說明，具有用於下限所需的比較的數量的說明一起，可以在這裏找到：

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

Answer 2

爲什麼要對字符串O（n log n）進行排序？

排序字符串中的字符不一定是O（n log n）。

• 爲O（n log n）的爲comparison sort的最佳值。這也是許多語言默認排序實現的複雜性。然而，當然可以做得比這更糟糕。排序字符串中字符的複雜程度取決於您選擇解決此任務的特定算法。
• 在某些情況下，通過使用不是比較排序的排序算法，也可以比O（n log n）做的更好。例如，如果你知道你有一個最多有127個不同字符的ASCII字符串，你可以使用一個counting sort，它是O（n）。對於所有字符位於Basic Multilingual Plane中的Unicode字符串，計數排序也是可行的。