delphi - QuickSort和堆栈溢出异常

我认为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;

预先感谢您的建议！

马吕斯

最佳答案

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

使用随机元素意味着退化只能通过纯粹的倒霉而发生（假设RNG无法由假设的攻击者预测到），因此这是一个很好的策略。要显着降低遭受这种不幸影响的可能性的另一项改进是使用3个（或5个或更多）随机选择的元素的中位数，但是必须权衡该元素的额外复杂性和运行时间。

关于delphi - QuickSort和堆栈溢出异常，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/944289/