2

我认为 QuickSort 在某些特定情况下可能会导致堆栈溢出异常。

在排序过程中有两种选择枢轴元素的基本方法 - 枢轴值可以是排序范围中间的元素或随机选择的元素（在排序范围内）。第二种方法（随机）是否比第一种方法更不容易发生堆栈溢出？你能告诉我吗？

这是我的快速排序（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;

提前感谢您的建议！

马吕斯。

4

4 回答 4

4

使用特定索引处的任何元素（第一个、最后一个或中间）作为枢轴元素总是会导致特定数据集退化的风险。第一个和最后一个元素特别糟糕，因为它们会随着预排序（或几乎预排序）的数据而退化，这很常见。中间元素在实践中问题较少，但仍然容易受到恶意构建的数据集的攻击。

使用随机元素意味着退化只能通过纯粹的运气来发生（假设 RNG 无法被假设的攻击者预测），所以这是一个很好的策略。进一步的改进可以显着降低被坏运气击中的可能性，即使用 3 个（或 5 个或更多）随机选择的元素的中位数，但必须权衡由此产生的额外复杂性和运行时间。

于 2009-06-03T12:11:09.950 回答
2

提高效率的一种概率方法是选择 3 个随机元素并使用中间值（不是最大也不是最小的那个）。

您还可以使用记录堆栈来推送和弹出边界并编写循环而不是进行递归调用（而且它会使用更少的内存，因为不需要为所有调用复制指向数组的指针）。

编辑：我注意到内部过程不将指针作为参数，所以忘记那部分^_^无论如何，堆栈帧比函数的参数有更多的信息，所以它会更节省内存（重点是分配数据堆栈的堆通常大于进程堆栈）。

于 2009-06-03T12:10:33.693 回答
0

感谢您的回答。

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;

我希望我以最佳方式实现它。我使用一个动态数组来存储排序边界（每对项目都是下限和上限）。

这种迭代方法似乎比递归方法稍慢，但我认为没那么重要。

如果您发现错误或您知道优化该方法的方法，如果您告诉我，我将不胜感激。

谢谢！

马吕斯。

于 2009-06-03T19:48:32.533 回答
0

一个不错的快速排序实现使用 O(log n) 堆栈空间。它通过首先对最小的子数组进行排序来实现这一点。如果您不这样做，最坏的情况是枢轴是最大元素并且您尝试对每次仅小一个的子数组进行排序。当您使用已排序的数据作为输入并将正确的元素作为枢轴时，就会发生这种情况。

您的显式堆栈实现较慢并且遇到同样的问题（尽管它现在是堆而不是堆栈）。

缺少的另一件事是当子数组很小（5-25 个元素）时切换到插入排序。还可以查看此站点上的双轴快速排序问题。

于 2010-01-20T23:45:02.120 回答