使用堆栈快速排序实现
我正在阅读下面链接中使用堆栈的快速排序实现。使用堆栈快速排序实现
我的问题是关于下面的段落。
把小的子文件较大堆栈 上的政策，确保堆栈上的每个条目是 大小它下面的一个的不超过一半，使堆栈需要包含 只有约lg N条目的空间。当 分区始终位于文件的中心时，会发生此最大堆栈使用情况。对于随机文件， 实际的最大堆栈大小要低得多;对于退化文件，它 可能很小。
此技术不一定在真正递归的 实现中工作，因为它取决于末尾递归或尾递归移除。 如果某个过程的最后一个动作是调用另一个过程，则某些编程环境将安排这样的事情，即在调用之前而不是之后从堆栈中清除本地变量 。 如果没有末端递归移除，我们无法保证堆栈大小 对于快速排序而言会很小。
是什么笔者通过“的堆栈上的每个条目是它下面的一个规模不超过二分之一”是什么意思？你能举一个这样的例子吗？
作者如何得出结论：堆栈只需要大约
lg N条目的空间？authore是什么意思？“没有结束递归移除，我们无法保证堆栈大小对于快速排序来说很小”？
感谢您的时间和帮助。
将较大的小型子文件放在堆栈上的策略可确保每个在堆叠上的入口不超过其下一个的大小的一半，
这不完全正确。考虑你想排序一个100个元素的数组，并且第一个数据中心在右边。然后你有一个堆栈
49
50
然后你弹出49个元素的部分离开堆栈，分区，并推动堆栈上的两个部分。假设这次枢轴的选择不太好，有20个元素不大于枢轴。然后你会得到堆栈
20
28
50
并且每个堆栈条目都超过下面的一半。
但不能永远持续下去，我们有
在整个分选，如果堆栈水平
k被占用，其规模至多total_size/(2^k)。
，当排序开始，从此只有一个在栈上元件，在0电平，这是大小total_size的整个阵列显然是正确的。
现在，假设声明的属性在进入循环（while(!stack.empty())）时保持不变。
从堆栈级别m中弹出长度为s的子数组。如果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 RESP。 m+1在循环体的末尾。不变量适用于下一次迭代。由于至多有一个大小为0的子阵列在堆栈中（它会在下一次迭代中立即弹出），因此绝对不会有超过lg total_size + 1的堆栈级别被占用。
关于
什么是笔者的“无尾递归去除，我们不能保证堆栈大小将是小的快速排序”是什么意思？
在递归实现中，您可以进行深度递归，并且当堆栈帧未被重新用于结束调用时，您可能需要线性堆栈空间。考虑一个愚蠢的枢轴选择，总是选择第一个元素作为枢轴，并选择一个已排序的数组。
[0,1,2,3,4]
分区，转轴位置为0，较小的子阵列为空。递归调用更大的子阵列[1,2,3,4]，分配一个新的堆栈帧（所以现在有两个堆栈帧）。同样的原理，下一个递归调用与子阵列[2,3,4]分配第三个堆栈帧等。
如果有一个已经结束递归移除，即堆栈帧被重新使用，则具有与上述手动堆栈相同的保证。
我会尽力回答你的问题（希望我没错）... 快速排序中的每一步都将输入分成两部分（一半）。通过这样做，你需要logN。这解释了您的第一个和第二个问题（“堆栈中的每个条目不超过一半”和“logN”条目）
在引用之前，你需要一些背景知识。 – UmNyobe