快速排序 - 哪個子部分應該先排序？

Question

我讀一些文字，聲稱這對於兩個遞歸快速排序的順序調用：

...它首先調用較小的子問題，這與尾遞歸結合是很重要的保證堆棧深度是log n。

我完全不知道這意味着什麼，爲什麼我應該首先在更小的子數組上調用Quicksort？

Answer 1

理想情況下，該列表被分成兩個大致相似大小的子列表。首先你工作的子列表並不重要。

但是，如果在一個糟糕的一天，在最不平衡的方式列表分區可能，幾乎只要原來的兩個或三個項目，也許4個，子表的子列表。這可能是由於分區價值選擇不當或者數據不合理。想象一下，如果你先處理更大的子列表，會發生什麼。 Quicksort的第一次調用是在棧幀中爲短列表保存指針/索引，同時遞歸調用長列表的quicksort。這也分爲很短的列表和很長的一個，我們首先做更長的子列表，重複...

最終，在惡劣數據最糟糕的日子最糟糕的時候，我們會有堆棧構建的幀數與原始列表長度成正比。這是快速排序最差的情況，遞歸調用的深度爲O（n）。 （請注意，我們說的遞歸，而不是性能的快速排序的深度。）

做短子表首先得到相當迅速擺脫它。我們仍然處理更多的小列表，與原始列表長度成比例，但現在每個小列表都由一個或兩個遞歸調用來處理。我們仍然進行O（n）調用（性能），但每個都是深度O（1）。

Answer 2

有些語言有尾遞歸。這意味着如果你編寫f（x）{... ... .. .. g（x）}，那麼對g（x）的最終調用並不是通過函數調用實現的，但是有一個跳轉，所以最終的調用不會使用任何堆棧空間。

快速排序將要排序的數據分爲兩部分。如果您總是首先處理較短的部分，那麼每個使用堆棧空間的調用都會有一段數據進行排序，該數據的大小至多是調用它的遞歸調用的一半。因此，如果您從10個元素開始排序，那麼最深處的堆棧將對這10個元素進行排序，然後是一個最多排序5個元素的調用，然後是一個最多排序2個元素的調用，然後是一個調用排序最多1個元素 - 然後，對於10個元素，堆棧不能再深入 - 堆棧大小受到數據大小日誌的限制。

如果你不擔心這個問題，你最終可能會拿着一個調用排序10個元素的堆棧，然後一個調用排序9個元素，然後一個調用排序8個元素，等等，這樣堆棧與要排序的元素數量一樣深。但是，如果你首先對短節進行排序，這種情況不會發生，因爲儘管你可以將10個元素分成1個元素和9個元素，但是排序9個元素的調用最後完成並且作爲跳轉來實現， t使用更多的堆棧空間 - 它重用先前由調用者使用的堆棧空間，該堆棧空間即將返回。

Answer 3

出人意料的是，這個結果是重要的，即使快速排序是不是面臨着瘋狂不平衡分區，即使實際使用內省排序。

問題出現（在C++）時進行排序，在容器中的值是非常大的。由此，我不是說他們指向真正的大對象，而是他們自己真的很大。在這種情況下，一些（可能很多）編譯器會使遞歸堆棧框架相當大，因爲它需要至少一個臨時值才能進行交換。 Swap在分區內被調用，它本身不是遞歸的，所以你會認爲quicksort遞歸驅動不需要怪物棧幀;不幸的是，分區通常最終被內聯，因爲它很好而且很短，並且不會在其他地方被調用。

通常情況下，20和40堆棧幀之間的差異可以忽略不計，但是如果這些值權重爲8kb，那麼20和40堆棧幀之間的差異可能意味着工作和堆棧溢出之間的差異，已經縮小尺寸以允許多個線程。

如果您使用「始終遞歸到較小的分區」算法，堆棧不能超過N幀，其中N是向量中元素的數量。此外，N不能超過可用內存量除以元素大小。因此，一個32位機器上，則只能有2個在載體8KB元件，並且快速排序呼叫深度不能超過19

總之，寫入快速排序正確地使得其堆棧使用預見 （只要你可以預測堆棧幀的大小）。即使在非病理情況下，不用擔心優化（以節省單個比較！）可以容易地導致堆棧深度增加一倍，並且在病理情況下，它會變得更糟。

Answer 4

將quicksort視爲隱式二叉樹。樞軸是根，左側和右側的子樹是您創建的分區。

現在考慮對該樹進行深度優先搜索。遞歸調用實際上對應於在上述隱式樹上進行深度優先搜索。同樣假定樹總是有較小的子樹作爲左邊的子樹，所以建議實際上是在這棵樹上進行預定。

現在假設你實現使用堆棧，你推只有左子序（但保留堆棧上的父），並在時機成熟時推右孩子（說你保持在那裏，你知道是否狀態一個節點有或沒有它的左邊的子節點），你替換堆棧的頂端，而不是推動右邊的子節點（這對應於尾遞歸部分）。

的最大堆棧深度是最大的「左深度」：如果您標記每個邊緣去左子爲1，將右子爲0，即，那麼你正在尋找具有最大總和的路徑邊緣（基本上你不會計算正確的邊緣）。

現在，由於左子樹的元素不超過一半，所以每次你離開時（即遍歷和邊標爲1），你都將剩下的探索節點的數量減少了至少一半。

因此，您看到標記爲1的最大邊數不超過log n。

因此，如果您總是選擇較小的分區並使用尾遞歸，那麼堆棧使用不會超過log n。