快速排序和堆棧溢出異常

Question

我認爲QuickSort在某些特定情況下可能會導致堆棧溢出異常。

在排序過程中，有兩種基本的方式選擇pivot元素 - pivot值可以是排序範圍中間的元素或隨機選擇的元素（在排序範圍內）。第二種方法（隨機）比第一種方法更容易發生堆棧溢出嗎？你能告訴我嗎？

這裏是我的版本快速排序（德爾福）的：

procedure QuickSort(lLowBound, lHighBound: integer; lCompare: TListSortCompare; 
    lSwap: TListSortSwap); 

    procedure Sort(lLowIndex, lHighIndex: integer); 
    var 
    lLeft: Integer; 
    lRight: Integer; 
    lPivot: Integer; 
    lLeftCompare: Integer; 
    lRightCompare: Integer; 
    begin 
    repeat 
     lLeft := lLowIndex; 
     lRight := lHighIndex; 
     lPivot := (lLowIndex + lHighIndex) div 2; //the pivot as the element in the middle 
     //lPivot := lLowIndex + Random(lHighIndex - lLowIndex + 1); //the pivot chosen randomly 
     repeat 
     lLeftCompare := lCompare(lLeft, lPivot); 
     while lLeftCompare < 0 do 
     begin 
      Inc(lLeft); 
      lLeftCompare := lCompare(lLeft, lPivot); 
     end; 
     lRightCompare := lCompare(lRight, lPivot); 
     while lRightCompare > 0 do 
     begin 
      Dec(lRight); 
      lRightCompare := lCompare(lRight, lPivot); 
     end; 

     if lLeft <= lRight then 
     begin 
      if not ((lLeftCompare = 0) and (lRightCompare = 0)) then 
      begin 
      lSwap(lRight, lLeft); 

      if lPivot = lLeft then 
       lPivot := lRight 
      else if lPivot = lRight then 
       lPivot := lLeft; 
      end; 
      Inc(lLeft); 
      Dec(lRight); 
     end; 
     until lLeft > lRight; 

     if (lLowIndex < lRight) then 
     Sort(lLowIndex, lRight); 

     lLowIndex := lLeft; 
    until lLeft >= lHighIndex; 
    end; 

begin 
    if lHighBound > lLowBound then 
    Sort(lLowBound, lHighBound); 
end; 

謝謝你的建議提前！

Mariusz。

Answer 1

使用特定索引（第一，最後或中間）的任何元素作爲主元素總是會導致具有特定數據集的退化風險。第一個和最後一個元素特別糟糕，因爲它們隨着預分類（或接近預分類）的數據退化，這是很常見的。中間元素在實踐中問題較少，但仍然易受惡意構建的數據集的影響。

使用隨機元素意味着退化只能通過純運氣發生（假設RNG不能被假設的攻擊者預測），所以這是一個很好的策略。進一步的改進可以顯着降低被運氣不好所擊中的可能性，即使用3個（或5個或更多）隨機選擇元素的中位數，但必須對這種附加複雜性和運行時間進行加權。

Answer 2

提高效率的概率方法是挑選3個隨機元素並使用中間值（不是最大值也不是最小值）。

你也可以使用一堆記錄來推動和彈出邊界並寫一個循環，而不是進行遞歸調用（也會使用較少的內存，因爲指向數組的指針不需要爲所有的調用）。

編輯：我注意到，內部過程不採取指針作爲參數，所以忘記部分^ _ ^無論如何，堆棧幀有更多的信息，而不僅僅是函數的參數，所以它會更高的內存效率（主要是堆分配的數據堆棧通常比進程堆棧​​大）。

Answer 3

感謝您的回答。

Fortran，感謝您提出有關制定非遞歸方法的建議。基於他們，我設法做出了一個迭代式快速排序，它似乎正常工作:)。

下面的代碼：

procedure QuickSortI(lLowBound, lHighBound: integer; lCompare: TListSortCompare; 
    lSwap: TListSortSwap); 
var 
    lLeft: Integer; 
    lRight: Integer; 
    lPivot: Integer; 
    lLeftCompare: Integer; 
    lRightCompare: Integer; 
    lStack: array of integer; 
    lStackLen: integer; 
begin 
    if lHighBound > lLowBound then 
    begin 
    lStackLen := 2; 
    SetLength(lStack, lStackLen); 
    lStack[lStackLen - 1] := lLowBound; 
    lStack[lStackLen - 2] := lHighBound; 

    repeat 
     lLowBound := lStack[lStackLen - 1]; 
     lHighBound := lStack[lStackLen - 2]; 
     SetLength(lStack, lStackLen - 2); 
     Dec(lStackLen, 2); 

     lLeft := lLowBound; 
     lRight := lHighBound; 
     lPivot := (lLowBound + lHighBound) div 2; 
     repeat 
     lLeftCompare := lCompare(lLeft, lPivot); 
     while lLeftCompare < 0 do 
     begin 
      Inc(lLeft); 
      lLeftCompare := lCompare(lLeft, lPivot); 
     end; 
     lRightCompare := lCompare(lRight, lPivot); 
     while lRightCompare > 0 do 
     begin 
      Dec(lRight); 
      lRightCompare := lCompare(lRight, lPivot); 
     end; 

     if lLeft <= lRight then 
     begin 
      if not ((lLeftCompare = 0) and (lRightCompare = 0)) then 
      begin 
      lSwap(lRight, lLeft); 

      if lPivot = lLeft then 
       lPivot := lRight 
      else if lPivot = lRight then 
       lPivot := lLeft; 
      end; 
      Inc(lLeft); 
      Dec(lRight); 
     end; 
     until lLeft > lRight; 

     if (lHighBound > lLeft) then 
     begin 
     Inc(lStackLen, 2); 
     SetLength(lStack, lStackLen); 
     lStack[lStackLen - 1] := lLeft; 
     lStack[lStackLen - 2] := lHighBound; 
     end; 

     if (lLowBound < lRight) then 
     begin 
     Inc(lStackLen, 2); 
     SetLength(lStack, lStackLen); 
     lStack[lStackLen - 1] := lLowBound; 
     lStack[lStackLen - 2] := lRight; 
     end; 

    until lStackLen = 0; 
    end; 
end; 

我希望我實現它以最佳的方式。我使用動態數組來存儲排序邊界（每對項目是低和高界限）。

這種迭代方法似乎比遞歸方法稍慢，但我認爲這並不重要。

如果您發現有錯誤或者您知道優化方法的方法，我將不勝感激，如果您讓我知道。

謝謝！

Mariusz。

Answer 4

體面的快速排序實現使用O（log n）堆棧空間。它通過首先排序最小的子數組來實現這一點。最糟糕的情況是，如果你不這樣做的話，那就是數據透視表是最大的元素，你嘗試對每次只有一個較小的子數組進行排序。當您使用已排序的數據作爲輸入並將右元素作爲支點時，會發生這種情況。

你的顯式堆棧實現比較慢，並且存在同樣的問題（雖然它現在是堆而不是堆棧）。

缺少的另一件事是當子陣列很小（5-25個元素）時切換到插入排序。另請看看本網站上的雙樞軸快速排序問題。