对数组排序的最佳方法

可以将指向数组元素的指针添加到 TList 然后调用 TList.Sort 使用比较函数,最后创建一个新数组,并按所需顺序将值从tlist中复制出来。

但是,如果您使用的是下一个版本D2009,那么有一个新的集合库可以对数组进行排序。它需要一个可选的 IComparer<TExample> 自定义排序顺序的实现。以下是针对您的具体案例而采取的行动:

TArray.Sort<TExample>(SomeVar , TDelegatedComparer<TExample>.Construct(
  function(const Left, Right: TExample): Integer
  begin
    Result := TComparer<Integer>.Default.Compare(Left.SortOrder, Right.SortOrder);
  end));

(我知道这是一年后的事,但仍然有用。)

skamradt关于填充整数值的建议假定您将使用字符串比较进行排序。这会很慢。为每个插入调用format(),速度仍然较慢。相反,您需要进行整数比较。

从记录类型开始:

TExample = record
  SortOrder : integer;
  SomethingElse : string;
end;

您没有说明记录是如何存储的,或者您希望在排序后如何访问它们。所以假设您将它们放入动态数组中:

var MyDA  Array of TExample; 
...
  SetLength(MyDA,NewSize);           //allocate memory for the dynamic array
  for i:=0 to NewSize-1 do begin        //fill the array with records
    MyDA[i].SortOrder := SomeInteger;
    MyDA[i].SomethingElse := SomeString;
  end;

现在您要按整数值sortorder对这个数组进行排序。如果您想要的是一个tstringlist(这样您就可以使用ts.find方法),那么您应该将每个字符串添加到列表中,并将sortorder作为指针添加。然后按指针排序:

var  tsExamples: TStringList;         //declare it somewhere (global or local)
...
  tsExamples := tStringList.create;   //allocate it somewhere (and free it later!)
...
  tsExamples.Clear;                   //now let's use it
  tsExamples.sorted := False;         //don't want to sort after every add
  tsExamples.Capacity := High(MyDA)+1 //don't want to increase size with every add
                                      //an empty dynamic array has High() = -1
  for i:=0 to High(MyDA) do begin
    tsExamples.AddObject(MyDA[i].SomethingElse,TObject(MyDA[i].SortOrder));
  end;

注意将整数sortOrder转换为存储在tstringlist.object属性中的tobject指针的技巧。(这取决于整数和指针大小相同的事实。)在某些地方,我们必须定义一个函数来比较tobject指针:

function CompareObjects(ts:tStringList; Item1,Item2: integer): Integer;
var i,j: integer;
begin
  Result := integer(ts.Objects[i]) - integer(ts.Objects[j];
end;

现在,我们可以通过调用.customsort而不是.sort(它将根据字符串值排序)对.object上的tslist进行排序。

tsExample.CustomSort(@CompareObjects);     //Sort the list

tstringlist现在已经排序,所以您可以从0迭代到.count-1并按排序顺序读取字符串。

但是假设您不想要一个tstringlist,只需要一个按顺序排列的数组。或者记录包含的数据比本例中的一个字符串多,排序顺序也更复杂。您可以跳过添加每个字符串的步骤,只需将数组索引添加为tlist中的项。除使用tlist而不是tstringlist外,其他所有操作都以相同的方式执行:

var Mlist: TList;                 //a list of Pointers
...
  for i:=0 to High(MyDA) do
    Mlist.add(Pointer(i));        //cast the array index as a Pointer
  Mlist.Sort(@CompareRecords);    //using the compare function below

function CompareRecords(Item1, Item2: Integer): Integer;
var i,j: integer;
begin
  i := integer(item1);            //recover the index into MyDA
  j := integer(item2);            // and use it to access any field
  Result := SomeFunctionOf(MyDA[i].SomeField) - SomeFunctionOf(MyDA[j].SomeField);
end;

现在,MList已排序,请将其用作查找表,以按排序顺序访问数组:

  for i:=0 to Mlist.Count-1 do begin
    Something := MyDA[integer(Mlist[i])].SomeField;
  end;

当我遍历tlist时,我们按排序顺序返回数组索引。我们只需要将它们转换回整数,因为tlist认为它们是指针。

我喜欢这样做,但是您也可以通过添加数组元素的地址而不是它的索引来将数组元素的实际指针放在tlist中。然后要使用它们,您可以将它们作为指向Texample记录的指针。这就是巴里·凯利和酷魔在回答问题时所说的。

如果需要按字符串排序,则使用排序 TStringList 和 添加记录 TString.AddObject(string, Pointer(int_val)) .

但如果需要按整型字段和字符串排序,请使用 TObjectList 添加所有记录后调用 TObjectList.Sort 以必要的排序函数作为参数。

这完全取决于您正在排序的记录的数量。如果您的排序少于几百个,那么其他排序方法工作得很好,如果您打算进行更多的排序,那么就好好看看以前值得信赖的涡轮动力。 SysTools 项目。源代码中包含一个非常好的排序算法。以一种有效的方式对数以百万计的记录进行分类的人。

如果要使用tstringlist方法对记录列表进行排序,请确保在将整数插入列表之前将其填充到右侧。你可以使用 格式(“%.10d”,[rec.sortorder]) 例如,右对齐到10位。

快速排序算法通常在需要快速排序时使用。Delphi正在(或曾经)使用它作为列表。例如排序。 DelphiList可以用于对任何内容进行排序,但它是一个重量级容器,应该看起来像结构上的指针数组。它是重量级的,即使我们在这个线程中使用像guy gordon这样的技巧(把索引或任何东西放在指针的位置上,或者直接把值放在小于32位的位置上):我们需要构造一个列表等等…

因此,对结构数组进行轻松快速排序的另一种方法可能是使用 qsort C runtime function 从msvcrt.dll。

下面是一个可能很好的声明(警告:代码只能在Windows上移植)。

type TComparatorFunction = function(lpItem1: Pointer; lpItem2: Pointer): Integer; cdecl;
procedure qsort(base: Pointer; num: Cardinal; size: Cardinal; lpComparatorFunction: TComparatorFunction) cdecl; external 'msvcrt.dll';

完整例子 here .

请注意,如果记录很大,直接对记录数组排序可能会很慢。在这种情况下,对指向记录的指针数组进行排序可以更快(以某种方式类似于列表方法)。

对于一个数组,我会使用 quicksort 或者可能 heapsort ,只需将比较结果更改为使用 TExample.SortOrder ,交换部分仍将仅作用于数组和交换指针。如果数组非常大,那么如果有大量的插入和删除,您可能需要一个链表结构。

基于C的例程,这里有几个 http://www.yendor.com/programming/sort/

另一个站点,但有Pascal源 http://www.dcc.uchile.cl/~rbaeza/handbook/sort_a.html

使用一种建议方式 Wikipedia . swap函数应使用与数组元素类型相同的临时变量交换数组元素。如果您希望具有相同sortOrder整数值的条目保持其最初的顺序,请使用稳定排序。

TStringList 有有效的排序方法。
如果要排序,请使用 列表列表 对象与 Sorted 属性设置为true。

注意:为了提高速度,请在“未排序”中添加对象 列表列表 最后将属性更改为true。
注意:对于“按整数排序”字段,请转换为字符串。
注意:如果有重复的值,则此方法无效。

当做。

如果您有Delphi XE2或更新版本,可以尝试:

var 
  someVar: array of TExample;
  list: TList<TExample>;
  sortedVar: array of TExample;
begin
  list := TList<TExample>.Create(someVar);
  try
    list.Sort;
    sortedVar := list.ToArray;
  finally
    list.Free;
  end;
end;

我创建了一个非常简单的示例,如果排序字段是一个字符串,它就可以正常工作。

Type
  THuman = Class
  Public
    Name: String;
    Age: Byte;
    Constructor Create(Name: String; Age: Integer);
  End;

Constructor THuman.Create(Name: String; Age: Integer);
Begin
  Self.Name:= Name;
  Self.Age:= Age;
End;

Procedure Test();
Var
 Human: THuman;
 Humans: Array Of THuman;
 List: TStringList;
Begin

 SetLength(Humans, 3);
 Humans[0]:= THuman.Create('David', 41);
 Humans[1]:= THuman.Create('Brian', 50);
 Humans[2]:= THuman.Create('Alex', 20);

 List:= TStringList.Create;
 List.AddObject(Humans[0].Name, TObject(Humans[0]));
 List.AddObject(Humans[1].Name, TObject(Humans[1]));
 List.AddObject(Humans[2].Name, TObject(Humans[2]));
 List.Sort;

 Human:= THuman(List.Objects[0]);
 Showmessage('The first person on the list is the human ' + Human.name + '!');

 List.Free;
End;