delphi - 快速排序戏剧

Question

我简直可以把头撞到墙上。我不明白为什么我的以下快速排序算法不起作用。它是用 Pascal 编写的:

program quicksort;

Type iArray = array [0..8] of integer;
var intArray, newArray : iArray;

Function getIntArray(localIntArray : iArray) : iArray;
begin
  localIntArray[0] := 3;
  localIntArray[1] := 1;
  localIntArray[2] := 8;
  localIntArray[3] := 4;
  localIntArray[4] := 9;
  localIntArray[5] := 0;
  localIntArray[6] := 8;
  localIntArray[7] := 2;
  localIntArray[8] := 5;
  getIntArray := localIntArray;
end;

Procedure writeArray(localIntArray : iArray);
var i:integer;
begin
  for i:=low(localIntArray) to high(localIntArray) do begin
      write(localIntArray[i]);
  end;
  writeln('');
end;

Procedure quicksort(links : integer ; rechts:integer; localIntArray : iArray); 
// links:      Index des 1. Elements, rechts: Index des letzten Elements
var l, r, pivot, pivotValue, temp : Integer;


    Function swap (larray : iArray; links :integer; rechts:integer) : iArray;                                 
    // Ich tausche in einem IntegerArray die Positionen links und rechts
    var temp : integer;
    begin
        temp                    := larray[links];
        larray[links]           := larray[rechts];
        larray[rechts]          := temp;
        swap                    := larray;
    end;

begin
  if (rechts>links) then begin
    l:= links;
    r:= rechts;
    pivot := localIntArray[(rechts+links) div 2];

    while (l<r) do begin
       while localIntArray[l] < pivot do l:=l+1;
       while localIntArray[r] > pivot do r:=r-1;
       if (l<=r) then begin
         localIntArray := swap(localIntArray,l,r);
         l := l+1;
         r := r-1;
       end;
    end;

    if (links < r) then quicksort(links, r, localIntArray);
    if (rechts > l) then quicksort(l, rechts, localIntArray);

    writeln('s Array: ');
    writeArray(localIntArray);
  end;
end;

var i : integer;
begin

  intArray := getIntArray(intArray);
  writeln('Unsortiertes Array: ');
  writeArray(intArray);
  quicksort(low(intArray), high(intArray), intArray);

end.

当我输入数组时:3,1,8,4,9,0,8,2,5 我收到以下计算结果:

0,1,2,3,5,4,8,8,9 -> 0,1,2,3,5,4,8,8,9 -> 3,1,2,0,4,5,8,8,9 -> 3,1,2,0,4,5,8,8, 9 -> 3,1,2,0,4,5,8,8,9 -> 3,1,2,0,5,4,8, 8,9 -> 3,1,8,4,5,0,8,2,9

这里发生了什么？

Answer 1

您的程序失败，因为您对数组的副本进行操作，而不是就地操作。因此考虑一下 quicksort 的声明:

Procedure quicksort(links, rechts: integer; localIntArray: iArray);

数组按值传递。您将数组传递到过程中，但调用者永远不会看到对数组所做的任何更改。相反，您需要通过传递对数组的引用来就地操作。这是一个 var 参数:

Procedure quicksort(links, rechts: integer; var localIntArray: iArray);

您需要对 swap 过程执行同样的操作，该过程应如下声明:

Procedure swap(var larray: iArray; links, rechts: integer);

这是一个正确排序的完整程序:

program quicksort24335585;

Type
  iArray = array [0 .. 8] of integer;

var
  intArray: iArray;

Function getIntArray(localIntArray: iArray): iArray;
begin
  localIntArray[0] := 3;
  localIntArray[1] := 1;
  localIntArray[2] := 8;
  localIntArray[3] := 4;
  localIntArray[4] := 7;
  localIntArray[5] := 0;
  localIntArray[6] := 8;
  localIntArray[7] := 2;
  localIntArray[8] := 5;
  getIntArray := localIntArray;
end;

Procedure writeArray(localIntArray: iArray);
var
  i: integer;
begin
  for i := low(localIntArray) to high(localIntArray) do
  begin
    write(localIntArray[i], ' ');
  end;
  writeln('');
end;

Procedure quicksort(links: integer; rechts: integer; var localIntArray: iArray);
// links:      Index des 1. Elements, rechts: Index des letzten Elements
var
  l, r, pivot: integer;

  procedure swap(var larray: iArray; links: integer; rechts: integer);
  // Ich tausche in einem IntegerArray die Positionen links und rechts
  var
    temp: integer;
  begin
    temp := larray[links];
    larray[links] := larray[rechts];
    larray[rechts] := temp;
  end;

begin
  if (rechts > links) then
  begin
    l := links;
    r := rechts;
    pivot := localIntArray[(rechts + links) div 2];

    while (l < r) do
    begin
      while localIntArray[l] < pivot do
        l := l + 1;
      while localIntArray[r] > pivot do
        r := r - 1;
      if (l <= r) then
      begin
        swap(localIntArray, l, r);
        l := l + 1;
        r := r - 1;
      end;
    end;

    if (links < r) then
      quicksort(links, r, localIntArray);
    if (rechts > l) then
      quicksort(l, rechts, localIntArray);
  end;
end;

begin
  intArray := getIntArray(intArray);
  writeln('Unsortiertes Array: ');
  writeArray(intArray);

  quicksort(low(intArray), high(intArray), intArray);

  writeln('s Array: ');
  writeArray(intArray);

  Readln;
end.

输出

Unsortiertes Array:
3 1 8 4 7 0 8 2 5
s Array:
0 1 2 3 4 5 7 8 8

我非常确定该程序可以得到完善和改进。这样做将成为您学习曲线的一部分!