algorithm - 快速排序 - 应该首先对哪个子部分进行排序？

Question

我正在阅读一些关于两个递归快速排序调用的排序的文本：

...首先调用较小的子问题很重要，这与尾递归相结合可确保堆栈深度为 log n。

我完全不确定这意味着什么，为什么我要先在较小的子数组上调用 Quicksort？

Answer 1

将快速排序视为隐式二叉树。枢轴是根，左右子树是您创建的分区。

现在考虑对这棵树进行深度优先搜索。递归调用实际上对应于对上述隐式树进行深度优先搜索。还假设树总是有较小的子树作为左孩子，所以建议实际上是在这棵树上做一个预排序。

现在假设您使用堆栈实现预排序，您只推送左子节点（但将父节点保留在堆栈中），以及何时推送右子节点（假设您保持一个状态，您知道一个节点是否有它的左孩子探索与否），你替换堆栈的顶部，而不是推动右孩子（这对应于尾递归部分）。

最大堆栈深度是最大“左深度”：即，如果您将前往左孩子的每条边标记为 1，将前往右孩子的每条边标记为 0，那么您正在查看具有最大边总和的路径（基本上您不要计算右边缘）。

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

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

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

Answer 2

Some languages have tail recursion. This means that if you write f(x) { ... ... .. ... .. g(x)} then the final call, to g(x), isn't implemented with a function call at all, but with a jump, so that the final call does not use any stack space.

Quicksort splits the data to be sorted into two sections. If you always handle the shorter section first, then each call that consumes stack space has a section of data to sort that is at most half the size of the recursive call that called it. So if you start off with 10 elements to sort, the stack at its deepest will have a call sorting those 10 elements, and then a call sorting at most 5 elements, and then a call sorting at most 2 elements, and then a call sorting at most 1 element - and then, for 10 elements, the stack cannot go any deeper - the stack size is limited by the log of the data size.

If you didn't worry about this, you could end up with the stack holding a call sorting 10 elements, and then a call sorting 9 elements, and then a call sorting 8 elements, and so on, so that the stack was as deep as the number of elements to be sorted. But this can't happen with tail recursion if you sort the short sections first, because although you can split 10 elements into 1 element and 9 elements, the call sorting 9 elements is done last of all and implemented as a jump, which doesn't use any more stack space - it reuses the stack space previously used by its caller, which was just about to return anyway.

Answer 3

理想情况下，该列表划分为两个大小大致相似的子列表。您首先处理哪个子列表并不重要。

但是，如果在糟糕的日子里，列表以最不平衡的方式划分，一个包含两个或三个项目的子列表，可能是四个，并且一个子列表几乎和原来的一样长。这可能是由于分区值的错误选择或恶意设计的数据造成的。想象一下，如果你先处理更大的子列表会发生什么。快速排序的第一次调用是在其堆栈帧中保存短列表的指针/索引，同时递归地为长列表调用快速排序。这也严重划分为一个非常短的列表和一个很长的列表，我们先做更长的子列表，重复......

最终，在最糟糕的最糟糕的日子里，我们将建立与原始列表长度成正比的堆栈帧。这是快速排序最坏的情况，递归调用的 O(n) 深度。（注意我们说的是快速排序的递归深度，而不是性能。）

首先做较短的子列表可以很快地摆脱它。我们仍然处理大量的小列表，与原始列表长度成比例，但现在每个列表都由浅的一两个递归调用处理。我们仍然进行 O(n) 次调用（性能），但每次调用的深度都是 O(1)。

Answer 4

令人惊讶的是，即使快速排序没有遇到严重不平衡的分区，甚至当实际使用 introsort 时，这也很重要。

当正在排序的容器中的值非常大时，就会出现问题（在 C++ 中）。我的意思并不是说它们指向非常大的物体，而是它们本身非常大。在这种情况下，一些（可能很多）编译器也会使递归堆栈帧变得非常大，因为它至少需要一个临时值才能进行交换。Swap 在分区内部调用，它本身不是递归的，因此您会认为快速排序递归驱动程序不需要怪物堆栈帧；不幸的是， partition 通常最终会被内联，因为它又好又短，并且不会从其他任何地方调用。

通常 20 和 40 个堆栈帧之间的差异可以忽略不计，但如果值的重量为 8kb，那么 20 和 40 个堆栈帧之间的差异可能意味着工作和堆栈溢出之间的差异，如果堆栈的大小已减小允许许多线程。

如果使用“总是递归到较小的分区”算法，堆栈不能每次超过 log ₂ N 帧，其中 N 是向量中的元素数。此外，N 不能超过可用内存量除以元素的大小。所以在 32 位机器上，一个向量中只能有 2 个¹⁹ 8kb 元素，并且快速排序调用深度不能超过 19。

简而言之，正确编写快速排序使其堆栈使用可预测（只要您可以预测堆栈帧的大小）。即使在非病态的情况下，不考虑优化（以保存单个比较！）也很容易导致堆栈深度加倍，并且在病态的情况下它会变得更糟。