如何在Delphi中实现快速排序，而不会为大量记录获取访问冲突错误？ [英] How can I implement a quick sort in Delphi without getting Access violation errors for large numbers of records?

问题描述

这是我当前的代码：

function StudentQuickSort(StudentList:TStudentArray;ArrayLength:integer):TStudentArray;
var
  Pivot:TstudentArray;
  LesserList:TStudentArray;
  GreaterList:TstudentArray;
  ArrayCount:Integer;
  LesserCount:Integer;
  GreaterCOunt:integer;
procedure ConcatArrays(const A,B,C: TStudentArray; var D: TStudentArray);
  var i, nA,nB,nC: integer;
  begin
    nA := length(A);
    nB := length(B);
    nC := Length(C);
    SetLength(D,nA+nB+nC);
    for i := 0 to nA-1 do
      D[i] := A[i];
    for i := 0 to nB-1 do
      D[i+nA] := B[i];
    for i := 0 to nC-1 do
      D[i+nA+nB] := C[i];
  end;

begin
  if Arraylength<=1 then
    begin
      Result:=(StudentList);
    end
  else
    begin
      SetLength(StudentList,ArrayLength);
      SetLength(LesserList,ArrayLength);
      SetLength(GreaterList,ArrayLength);
      SetLength(Pivot,1);
      LesserCOunt:=0;
      GreaterCount:=0;
      Pivot[0]:=StudentList[0];
      for ArrayCount := 1 to ArrayLength-1 do
        begin
          if strtoint(StudentList[ArrayCount].StudentNo)>strtoint(Pivot[0].StudentNo) then
           begin
              GreaterList[GreaterCOunt]:=StudentList[ArrayCount];
              GreaterCount:=GreaterCount+1;
           end
         else
            begin
              LesserList[LesserCOunt]:=StudentList[ArrayCount];
              LesserCount:=LesserCount+1;
            end;
        end;
        SetLength(LesserLIst,LesserCount);
        SetLength(GreaterList,GreaterCount);
        ConcatArrays(StudentQuickSort(LesserList,LesserCount),Pivot,StudentQuickSort(GreaterList,GreaterCount),Result)
    end;
end;

如何稳定，尽可能少地更改代码。这是使用动态数组的问题吗？我需要能够对至少600条记录进行排序，无错误。

How can this be stabilized, ideally changing as little code as possible. IS it a problem with using dynamic arrays? I need to be able to sort through at least 600 records without error.

推荐答案

您的代码无法被抢救。你会以错误的方式解决这个问题，我建议你放弃现有的代码。这是我如何相信排序应该做的。

Your code cannot be salvaged. You are going about solving this problem in the wrong way and I advise you to abandon your existing code. Here is how I believe sorting should be done.

请注意，我假设您没有可用的泛型。在现代的Delphi版本中，您可以使用 Generics.Collections 中的 TArray.Sort< T> 进行排序。如果您有访问权限，您应该使用它

Note that I am assuming that you don't have generics available to you. In modern Delphi versions you can use TArray.Sort<T> from Generics.Collections to sort. If you have access to that, you should use it

首先，关键是将排序与正在排序的数组进行排序。要实现这一点，定义以下类型：

First of all the key is to separate the sorting from the array being sorted. To achieve that define the following types:

type
  TCompareIndicesFunction = function(Index1, Index2: Integer): Integer of object;
  TExchangeIndicesProcedure = procedure(Index1, Index2: Integer) of object;

重点是，可以排序数组的所有常见算法只需要能够比较两个物品，交换两件物品。这些过程类型使排序算法与底层数组存储和类型分离。

The point is that all the common algorithms that can sort an array need only to be able to compare two items, and exchange two items. These procedural types enable separation of the sorting algorithm from the underlying array storage and types.

通过这些定义，我们准备编写通用排序算法。对于快速排序，它看起来像这样：

With these definitions in place, we are ready to write our general purpose sorting algorithms. For quicksort it looks like this:

procedure QuickSort(Count: Integer; Compare: TCompareIndicesFunction; 
  Exchange: TExchangeIndicesProcedure);

  procedure Sort(L, R: Integer);
  var
    I, J, P: Integer;
  begin
    repeat
      I := L;
      J := R;
      P := (L+R) div 2;
      repeat
        while Compare(I, P)<0 do inc(I); 
        while Compare(J, P)>0 do dec(J); 
        if I<=J then 
        begin
          if I<>J then 
          begin
            Exchange(I, J);
            //may have moved the pivot so we must remember which element it is
            if P=I then
              P := J
            else if P=J then
              P := I;
          end;
          inc(I);
          dec(J);
        end;
      until I>J;
      if L<J then 
        Sort(L, J); 
      L := I;
    until I>=R;
  end;

begin
  if Count>0 then
    Sort(0, Count-1);
end;

为了使用它，您需要将数组包装在一个暴露比较和交换方法的类中。

In order to use this you need to wrap your array in a class which exposes compare and exchange methods.

这篇关于如何在Delphi中实现快速排序，而不会为大量记录获取访问冲突错误？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！