delphi - 快速排序和堆栈溢出异常

Question

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

感谢您提前提出建议!

马吕斯。

Answer 1

使用特定索引(第一个、最后一个或中间)处的任何元素作为主元元素总是会带来特定数据集退化的风险。第一个和最后一个元素特别糟糕，因为它们会随着预排序(或接近预排序)的数据而退化，这很常见。中间元素在实践中问题较少，但仍然容易受到恶意构建的数据集的影响。

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