2

我有很多节点以通常的方式存储在二叉树中，以便根据存储在每个节点中的某个值对它们进行排序；也就是说，可以从左到右递归遍历树并按排序顺序获得总集。

但是，我有一个大的单独的指针数组，指向树中节点的子集，并且该数组中的顺序是随机的。

我希望能够快速排序这个数组。有什么方法可以参考二叉树结构来加快速度吗？如有必要，我可以将成员添加到任何节点。

谢谢！

4

1 回答 1

1

通过在节点中添加一个标志，您可以获得运行时O(t+a)（t 是树的大小，a 是数组的大小）。这是通过首先在数组中设置标志然后遍历树并挑选出被标记的值来完成的。

这仅在您的树仅log a比数组大几倍时才有优势。如果 t>>a 快速排序肯定是首选方法，因为它的运行时间为O(a * log a).

于 2013-02-26T23:32:36.203 回答