快速排序和堆栈溢出异常

Question

我认为快速排序在某些特定条件下可能会导致堆栈溢出异常。

有在排序处理选择所述枢转元件的两种基本方式 - 枢轴值可以是在排序范围的中间或随机选择的（排序的范围内）的元素的元素。是第二方法（随机）少堆栈溢出比第一个容易？能否请你告诉我？

下面是我的快速排序（DELPHI）的版本：

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;

感谢提前您的咨询！

马里乌什。

Answer 1

在一个特定的索引使用任何元件（第一，最后或中间）作为枢轴元件总是招致变性的与特定的数据集的风险。因为他们用预先排序（或接近预分类）的数据，这是很常见的退化第一和最后一个元素特别恶劣。中间元件在实践中是问题较少，但仍易受恶意构造的数据集。

使用一个随机元素意味着变性只能通过纯粹的运气不好发生（假设RNG是不是一个假设攻击者可预测的），所以这是一个很好的策略。进一步的改进在于显著减少了由该坏运气被击中的可能性将是使用的3（或5个或更多）随机选择元素的中值，但它具有对额外的复杂性和运行时间这招致进行加权。

Answer 2

，以提高效率的概率的方法是挑选3个随机元素，并且使用中间值（一个不是最大的，也不是至少）。

您也可以使用一堆唱片，推动和流行的界限，并写一个循环，而不是把递归调用（它也将使用较少的内存，因为指针数组不会需要复制所有来电）。

编辑：我注意到，内部程序不走指针作为参数，所以忘记部分^ _ ^反正堆栈帧具有比所述功能的只是参数的更多信息，所以这将是仍然更存储器高效（和主点是，堆都被分配数据堆栈通常比进程栈大）。

Answer 3

谢谢您的回答。

Fortran语言，感谢您的关于使非递归方法的建议。此基础上他们，我设法让一个iterational快速排序，它似乎正常工作。）

下面的代码：

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;

我希望实现它以最佳的方式。我使用动态数组来存储排序边界（每对项目的是低和高结合）。

这iterational方法似乎比递归一个稍微慢一些，但我觉得它不那么重要了。

如果您发现有误，或者您知道优化方法的一种方式，我会很感激，如果你让我知道。

谢谢！

马里乌什。

Answer 4

一个体面的quicksort实现使用O（log n）的堆栈空间。它实现了，首先分拣最小的子阵。如果你不这样做，最坏的情况是情况枢轴是最大的元素，并尝试排序子数组只有一个较小的每次是。当使用已经排序的数据作为输入，并采取作为枢轴右侧元件发生这种情况。

您明确栈实现较慢，从相同的问题的困扰（虽然它现在是堆代替堆栈）。

丢失的另一件事是一个开关插入排序当子阵列是小（5-25元素）。也看看本网站上的双枢轴快速排序的问题。