我正在阅读以下链接中使用堆栈的快速排序实现。
我的问题是关于以下段落。
将较大的小子文件放在堆栈上的策略确保堆栈上的每个条目不超过其下一个条目大小的一半，因此堆栈只需要包含大约 lg N 个条目的空间. 当分区始终位于文件的中心时，会出现此最大堆栈使用量。对于随机文件，实际的最大堆栈大小要小得多；对于退化的文件，它可能很小。
这种技术不一定适用于真正的递归实现，因为它依赖于结束递归或尾递归的去除。如果一个过程的最后一个动作是调用另一个过程，一些编程环境会安排这样的事情，即在调用之前而不是之后从堆栈中清除局部变量。如果没有结束递归删除，我们不能保证堆栈大小对于快速排序来说会很小。
作者所说的“堆栈上的每个条目不超过其下方条目大小的一半”是什么意思？你能举个例子吗？
作者是如何得出堆栈只需要大约lg N条目的空间的结论的？
“如果没有结束递归删除，我们不能保证堆栈大小对于快速排序来说会很小”是什么意思？
感谢您的时间和帮助。
将较大的小子文件放入堆栈的策略确保堆栈上的每个条目不超过其下方条目大小的一半，
这并不完全正确。假设您要对一个 100 个元素的数组进行排序，并且第一个枢轴正好位于中间。然后你有一个堆栈
49
50
然后将 49 个元素的部分从堆栈中弹出，分区，然后将这两个部分压入堆栈。假设这次选择的枢轴不太好，有20个元素不大于枢轴。然后你会得到堆栈
20
28
50
并且每个堆栈条目是下面一个的一半以上。
但这不可能永远持续下去，我们有
在整个排序过程中，如果栈层
k被占用，其大小最多为total_size / (2^k).
这在排序开始时显然是正确的，因为那时堆栈上只有一个元素，位于第 0 级，即整个 size 数组total_size。
现在，假设所述属性在进入循环 ( while(!stack.empty())) 时保持不变。
s从栈层弹出一个长度为的子数组m。如果s <= 1，则在下一次循环迭代之前不做任何其他事情，并且不变量继续成立。否则，如果s >= 2， 分区之后，有两个新的子数组要被压入堆栈，并且s-1元素在一起。这两个中较小的有一个尺寸smaller_size <= (s-1)/2，而较大的有一个尺寸larger_size <= s-1。堆栈级别m将被两者中的较大者占用，我们有
larger_size <= s-1 < s <= total_size / (2^m)
smaller_size <= (s-1)/2 < s/2 <= total_size / (2^(m+1))
分别用于堆栈级别m。m+1在循环体的末尾。不变量适用于下一次迭代。
lg total_size + 1由于堆栈上最多有一个大小为 0 的子数组（然后在下一次迭代中立即弹出），因此占用的堆栈级别永远不会超过。
关于
作者所说的“没有结束递归删除，我们不能保证堆栈大小对于快速排序来说会很小”是什么意思？
在递归实现中，您可以进行深度递归，并且当堆栈帧未重用于结束调用时，您可能需要线性堆栈空间。考虑一个愚蠢的枢轴选择，总是选择第一个元素作为枢轴，以及一个已经排序的数组。
[0,1,2,3,4]
分区，枢轴进入位置 0，较小的子数组为空。对较大 subarray 的递归调用[1,2,3,4]分配了一个新的堆栈帧（因此现在有两个堆栈帧）。同样的原理，下一次递归调用子数组[2,3,4]分配第三个堆栈帧，等等。
如果一个有结束递归删除，即堆栈帧被重用，一个与上面的手动堆栈相同的保证。
我将尝试回答您的问题（希望我没有错）...快速排序的每一步都将您的输入分成两部分（一半）。通过这样做，您需要 logN。这解释了您的第一个和第二个问题（“堆栈上的每个条目不超过一半”和“logN”条目）