我正在阅读一些关于两个递归快速排序调用的顺序的文本:
... it is important to call the smaller subproblem first, this in conjunction with tail recursion ensures that the stack depth is log n.
我完全不确定那是什么意思，为什么我应该先在较小的子数组上调用快速排序？
最佳答案
将快速排序视为隐式二叉树。枢轴是根，左右子树是您创建的分区。
现在考虑对这棵树进行深度优先搜索。递归调用实际上对应于对上述隐式树进行深度优先搜索。还假设树总是有较小的子树作为左子树，所以建议实际上是在这棵树上进行预排序。
现在假设您使用堆栈实现预序，您只压入左子节点(但将父节点保留在堆栈中)，并且在需要时压入右子节点(假设您保持一种状态，您知道节点是否探索了它的左子节点)，您替换堆栈的顶部，而不是压入右子节点(这对应于尾递归部分)。
最大堆栈深度是最大“左深度”:即，如果您将每条通往左 child 的边标记为 1，将前往右 child 的每条边标记为 0，那么您正在查看具有最大边和的路径(基本上你不计算右边缘)。
现在，由于左子树的元素不超过一半，每次向左移动(即遍历和标记为 1 的边)，您都会将要探索的节点数减少至少一半。
因此，您看到的标记为 1 的边的最大数量不超过 log n。
因此，如果您始终选择较小的分区并使用尾递归，则堆栈使用量不会超过 log n。
关于algorithm - Quicksort - 哪个子部分应该首先排序？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12792738/