我很困惑为什么快速排序，shellsort，mergesort...所有反复提到的 O（nlog（n）） 算法都是流行的排序算法，二进制搜索树的无序遍历不会给树排序带来 O（n） 的复杂性吗？我错过了什么？
No.构建树具有 O（N log N） 复杂性（即，您将 N 个项目插入树中，并且每次插入都有对数复杂性）。
一旦你构建了树，你可以以线性复杂度遍历它（特别是如果它是一个线程树），但这并不等同于排序 - 它等效于在排序后遍历数组。
尽管它们具有相同的渐近复杂性，但构建树通常会慢一个很大的因素，因为您必须为树分配节点并遍历不连续分配的节点才能遍历树。
基本上有 6 种类型的复杂性。O（1），O（logn），O（n），O（nlogn），O（n^2），O（n^3）.
对于为什么流行的排序算法具有 O（nlogn） 复杂性的问题的第一部分，这仅仅是因为我们无法以 O（n） 复杂性对数组进行排序。这是因为对于 O（n） 复杂性，您只想在一个循环中对数组进行排序。这是不可能的，因为我们无法在一个连续中对数组进行排序。
所以下一个可能的复杂性是O（nlogn）。这就是划分和征服方法，例如在合并排序中我们发现中间元素递归地对每一面进行排序。对于递归，因为每次复杂度为 O（logn） 时，它的大小都会减少到一半。对于排序部分，它使O（nlogn）的复杂性。
对于问题的下一部分，请记住这样一个事实，即BST中的所有基本操作（如插入，删除）都具有O（logn）的复杂性，其中logn是树的高度。
因此，如果您使用 o（n） 复杂性对树进行排序，使其总计为 O（nlogn）。
如果你不明白我的意思，请评论我。我认为这是回答这个问题的简单方法。
二叉树的任何遍历都是 O（n）。但这不是排序。具有BST意味着它已经是一个排序的树。你只是在穿越它。构建BST是渐近O（nlog（n））的排序过程。请注意 O（n） +