我正在閱讀下面鏈接中使用堆棧的快速排序實現。使用堆棧快速排序實現
我的問題是關於下面的段落。
把小的子文件較大堆棧 上的政策，確保堆棧上的每個條目是 大小它下面的一個的不超過一半，使堆棧需要包含 只有約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