0

Delphi 在其中一个示例中实现了 QuickSort：

procedure QuickSort(var A: array of Integer; iLo, iHi: Integer);
var
  Lo, Hi, Mid, T: Integer;
begin
  Lo := iLo;
  Hi := iHi;
  Mid := A[(Lo + Hi) div 2];
  repeat
    while A[Lo] < Mid do Inc(Lo);
    while A[Hi] > Mid do Dec(Hi);
    if Lo <= Hi then
    begin
      VisualSwap(A[Lo], A[Hi], Lo, Hi); // just for visual
      T := A[Lo];
      A[Lo] := A[Hi];
      A[Hi] := T;
      Inc(Lo);
      Dec(Hi);
    end;
  until Lo > Hi;
  if Hi > iLo then QuickSort(A, iLo, Hi);
  if Lo < iHi then QuickSort(A, Lo, iHi);
  if Terminated then Exit;
end;

它有效，但分区似乎很奇怪。或者这是一个常见的优化？

我用随机值做了一个测试，你会得到 Mid 不在 Hi、Lo 或介于两者之间的情况。在这种情况下，“枢轴”在两个值之间。这是因为它会在翻转后同时增加 Lo 和 Hi，即使其中一个具有 Mid 值。是不是你持有 Pivot 值并在它的左侧和右侧进行另一个 QuickSort 的线索。这是对等键值的优化吗？

另外，这个实现是否存在等值问题？3路分区会更好吗？

4

3 回答 3

1

我还测试了中位数为 3 等的不同变体。唯一能加快速度的就是让它成为快速排序和插入排序之间的混合体，并展开其中一个递归。我删除了关键部分，因为它没有提供任何东西。这是我测试的最终变体：

procedure QuickSort3(var A: array of integer; iLo, iHi: integer);
var
  Hi, Lo, T, Mid: integer;
begin
  repeat
    if (iHi-iLo) > 16 then
    begin
      Mid := A[(iHi + iLo) shr 1];
      Lo := iLo;
      Hi := iHi;
      repeat
        while A[Lo] < Mid do inc(Lo);
        while A[Hi] > Mid do dec(Hi);
        if Lo <= Hi then
        begin
          if Lo <> Hi then
          begin
            T := A[Lo];
            A[Lo] := A[Hi];
            A[Hi] := T;
          end;
          inc(Lo);
          dec(Hi);
        end;
      until Hi < Lo;
      if Hi > iLo then
        QuickSort3(A,iLo,Hi);
      iLo := Lo;
    end
    else
    begin
      for Lo := iLo + 1 to iHi do
      begin
        T := Arr[Lo];
        Hi := Lo;
        while (Hi > iLo) and (Arr[Hi-1] > T) do
        begin
          Arr[Hi] := Arr[Hi-1];
          dec(Hi);
        end;
        Arr[Hi] := T;
      end;
      exit;
    end;
  until iHi <= Lo;
end;

1 亿个随机值的增益约为 1.4 秒。

无论如何，到目前为止我所学到的：

分区是正确的，您不需要处理密钥。许多 QuickSort 教程解释了这个“错误”。错误的方式是不需要它。

处理密钥几乎没有什么收获。你接到的电话少了一点，但你也会在额外的处理中受到惩罚，而且它们大致相同。总的来说，我在排序 1 亿个值（总共 13.9 秒）时的按键处理速度提高了 50-100 毫秒。但那是在 Delphi 编译器上。

当元素低于 16 时，插入排序足以在快速排序中使用。

于 2013-03-09T15:11:01.927 回答
0

请对此发表评论，因为我不确定这是一种更好的方法。

我试图理解 QuickSort 的本质。我认为这个更正会使这个实现更好地工作（忽略 VisualSwap，它仅用于演示视觉效果）：

procedure QuickSort(var A: array of Integer; iLo, iHi: Integer);
var
  Lo, Hi, Mid, T: Integer;
begin
  Lo := iLo;
  Hi := iHi;
  T := (Lo + Hi) div 2;
  VisualSwap(A[Lo], A[T], Lo, T);
  Mid := A[T];
  A[T] := A[Lo];
  A[Lo] := Mid;

  inc(Lo);
  //Mid := A[(Lo + Hi) div 2];
  repeat
    while A[Lo] < Mid do Inc(Lo);
    while A[Hi] > Mid do Dec(Hi);
    if Lo <= Hi then
    begin
      VisualSwap(A[Lo], A[Hi], Lo, Hi);
      T := A[Lo];
      A[Lo] := A[Hi];
      A[Hi] := T;
      Inc(Lo);
      Dec(Hi);
    end;
  until Lo > Hi;

  if Hi > iLo then
  begin
    VisualSwap(A[iLo],A[Hi],iLo,Hi);
    A[iLo] := A[Hi];
    A[Hi] := Mid;
    dec(Hi);
  end;

  if Hi > iLo then QuickSort(A, iLo, Hi);
  if Lo < iHi then QuickSort(A, Lo, iHi);
  if Terminated then Exit;
end;

我所做的是在找到枢轴的同时移出钥匙，然后将钥匙放在枢轴中，并且只在该关键点之外进行快速排序。

于 2013-03-09T12:45:05.843 回答
0

代码中的一个错误：

mid = (low + high) 使用最大整数附近的数组时，div 2 可能会溢出。

解决方法：mid = low div 2 + high div 2

有关详细讨论，请参阅算法

阅读该链接后，您应该知道：

这是对等键值的优化吗？

不，相等的值没有问题。（快速排序不是一种稳定的排序）

另外，这个实现是否存在等值问题？3路分区会更好吗？

没有问题。不，为什么它应该更好？可以使用随机枢轴元素选择来进行优化。

于 2013-03-09T12:59:54.880 回答