1

我必须对数组进行排序。除了已经存在的排序类型之外，我想知道这样的算法是否可行，以及它的复杂性可能是什么。

我有一个要排序的数组。我创建了一个二叉搜索树。

所以如果我将数组的所有元素都插入到BST中，然后在进行树的中序遍历时，将它们一个一个地赋值回数组，我将得到一个排序的结果。（尽管由于树节点而消耗了更多的空间复杂性。不是就地排序。）

int i=0;

void sort_by_inorder(node *n)
{
    if(n==NULL)
    {
        return;
    }
    sort_by_inorder(n->leftchild);
    array[i++]=n->data;
    sort_by_inorder(n->rightchild);
}

我知道 BST 不允许重复插入，所以也许我们可以考虑将 BST 插入算法修改为 <= 用于左子树，或者 >= 用于右子树。

这会是一个很好的实现（可行）吗？复杂度会是多少？

遍历复杂度是平均的O(n)。而插入只是O(log n). 因此，据我所知，这应该是一种有效的算法。

谢谢。

4

1 回答 1

0

在一般的二叉搜索树中，插入时间在最坏的情况下实际上是 O(n)。您需要一个平衡树才能使操作为 O(log(n))。

因此，在一般 BST 中，您的方法允许您在 O(n^2) 中进行排序。

于 2012-07-13T13:10:28.847 回答