Moe*_*oeb 9 sorting algorithm quicksort
我正在阅读一些文本声称有关两个递归Quicksort调用的顺序:
...首先调用较小的子问题很重要,这与尾递归一起确保堆栈深度为log n.
我完全不确定这意味着什么,为什么我应该首先在较小的子阵列上调用Quicksort？
小智 8
将quicksort看作隐式二叉树.pivot是根,左右子树是您创建的分区.
现在考虑对该树进行深度优先搜索.递归调用实际上对应于在上述隐式树上进行深度优先搜索.还假设树总是具有较小的子树作为左子,因此建议实际上是在该树上进行预订.
现在假设您使用堆栈实现预订单,其中您只推送左侧子节点(但将父节点保留在堆栈上)以及何时推送正确的子节点(假设您保持一个状态,您知道节点是否具有其左子探索与否),你替换堆栈的顶部,而不是推动右子(这对应于尾递归部分).
最大堆栈深度是最大"左深度":即,如果将每个边缘标记为左边的子节点为1,并将右边的子节点标记为0,则表示您正在查看具有最大边缘总和的路径(基本上是不计算正确的边缘).
现在,因为左子树的元素不超过一半,所以每次向左移动(即遍历和边缘标记为1),您将减少至少一半的剩余探测节点数.
因此,您看到的标记为1的最大边数不超过log n.
因此,如果您总是选择较小的分区,并使用尾递归,则堆栈使用量不会超过log n.
有些语言有尾递归.这意味着如果你写f(x){... ... .. ... .. g(x)}那么最后的调用,到g(x),根本没有用函数调用来实现,但是有一个跳转,所以最后的调用不使用任何堆栈空间.
Quicksort将要分类的数据拆分为两个部分.如果您总是首先处理较短的部分,那么每个使用堆栈空间的调用都有一个要排序的数据部分,它最多只是调用它的递归调用的一半大小.因此,如果您从10个元素开始排序,最深的堆栈将有一个调用排序这10个元素,然后调用排序最多5个元素,然后调用排序最多2个元素,然后调用排序最多1个元素 - 然后,对于10个元素,堆栈不能更深 - 堆栈大小受数据大小日志的限制.
如果你不担心这个,你可能最终得到一个调用排序10个元素的堆栈,然后调用排序9个元素,然后调用排序8个元素,依此类推,这样堆栈就像深作为要排序的元素数量.但是如果你首先对短节进行排序,这不会发生尾递归,因为虽然你可以将10个元素分成1个元素和9个元素,但最后完成调用排序9个元素并实现为跳转,这不是使用更多的堆栈空间 - 它重用其先前由其调用者使用的堆栈空间,无论如何它都将返回.
理想情况下，列表分为两个大小大致相似的子列表。您首先处理哪个子列表并不重要。
但是，如果在糟糕的一天，列表以最不平衡的方式进行分区，则子列表包含两个或三个项目，也许四个，并且子列表几乎与原始列表一样长。这可能是由于分区值的错误选择或恶意设计的数据造成的。想象一下如果您首先处理更大的子列表会发生什么。快速排序的第一次调用是将短列表的指针/索引保存在其堆栈帧中，同时递归地调用长列表的快速排序。这也很糟糕地划分为一个很短的列表和一个很长的列表，我们首先做较长的子列表，重复......
最终，在最糟糕的日子里，有最糟糕的数据时，我们将建立与原始列表长度成比例的堆栈帧。这是快速排序最坏情况的行为，递归调用的深度为 O(n)。（请注意，我们谈论的是快速排序的递归深度，而不是性能。）
首先执行较短的子列表可以很快地摆脱它。我们仍然按照原始列表长度的比例处理大量的小列表，但现在每个列表都由一到两个浅递归调用来处理。我们仍然进行 O(n) 次调用（性能），但每次调用的深度都是 O(1)。