快速排序-哪个子部分应该首先排序？ [英] Quicksort - which sub-part should be sorted first?

问题描述

我正在阅读一些有关两个递归Quicksort调用顺序的文字：

I am reading some text which claims this regarding the ordering of the two recursive Quicksort calls:

...先调用较小的子问题，再结合尾部递归操作，可确保堆栈深度为log n。

... it is important to call the smaller subproblem first, this in conjunction with tail recursion ensures that the stack depth is log n.

我一点也不知道这意味着什么，为什么我应该首先在较小的子数组上调用Quicksort？

I am not at all sure what that means, why should I call Quicksort on the smaller subarray first?

推荐答案

将quicksort视为隐式二叉树。枢轴是根，左和右子树是您创建的分区。

Look at quicksort as an implicit binary tree. The pivot is the root, and the left and right subtrees are the partitions you create.

现在，请考虑对该树进行深度优先搜索。递归调用实际上对应于在上述隐式树上进行深度优先搜索。还要假设该树始终具有较小的子树作为左子树，因此实际上建议对该树进行预订。

Now consider doing a depth first search of this tree. The recursive calls actually correspond to doing a depth first search on the implicit tree described above. Also assume that the tree always has the smaller sub-tree as the left child, so the suggestion is in fact to do a pre-order on this tree.

现在假设您可以使用堆栈来实现预定项，在堆栈中，您仅推入左子级（但将父级保留在堆栈中），并且当需要推入右子级时（例如，您保持了一个状态，即您知道节点是否有其左子级）

Now suppose you implement the preorder using a stack, where you push only the left child (but keep the parent on the stack) and when the time comes to push the right child (say you maintained a state where you knew whether a node has its left child explored or not), you replace the top of stack, instead of pushing the right child (this corresponds to the tail recursion part).

最大堆栈深度是最大堆栈深度，而不是探究的顶部，而不是推入正确的子级（这对应于尾部递归部分）。 左深度：即，如果将去往左孩子的每条边标记为1，将去往右孩子的每条边标记为0，那么您正在寻找的边的总和最大（基本上不计算右边的边） ）。

The maximum stack depth is the maximum 'left depth': i.e. if you mark each edge going to a left child as 1, and going to a right child as 0, then you are looking at the path with maximum sum of edges (basically you don't count the right edges).

现在，由于左子树的元素不超过一半，因此每次您左移（即遍历和标记为1的边）时，都将减少至少要研究的节点数t一半。

Now since the left sub-tree has no more than half the elements, each time you go left (i.e. traverse and edge marked 1), you are reducing the number of nodes left to explore by at least half.

因此，您看到的标记为1的边的最大数量不超过log n。

Thus the maximum number of edges marked 1 that you see, is no more than log n.

因此，如果您始终选择较小的分区，并使用尾部递归，则堆栈使用量不超过log n。

Thus the stack usage is no more than log n, if you always pick the smaller partition, and use tail recursion.

这篇关于快速排序-哪个子部分应该首先排序？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！