对数组进行排序的最佳方法

Question

假设我有一组记录，我想根据记录中的一个字段对其进行排序。实现这一目标的最佳方法是什么？

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

var SomeVar : array of TExample;

Answer 1

您可以将指向数组元素的指针添加到 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));

Answer 2

（我知道这是一年后的事了，但仍然有用。）

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;

请注意将 Integer SortOrder 转换为 TObject 指针的技巧，该指针存储在 TStringList.Object 属性中。（这取决于 Integer 和 Pointer 大小相同的事实。）我们必须在某个地方定义一个函数来比较 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 记录的指针。这就是 Barry Kelly 和 CoolMagic 在他们的回答中所说的要做的事情。

Answer 3

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

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

Answer 4

这一切都取决于您要排序的记录数量。如果您只排序少于几百个，那么其他排序方法就可以正常工作，如果您要排序更多，那么请仔细看看旧的值得信赖的 Turbo Power 系统工具 项目。源代码中包含一个非常好的排序算法。它能够很好地以有效的方式对数百万条记录进行排序。

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

Answer 5

当需要快速排序时，经常使用快速排序算法。例如，Delphi 正在（或曾经）将它用于 List.Sort。Delphi List 可用于对任何内容进行排序，但它是一个重量级容器，它应该看起来像结构上的指针数组。即使我们在这个线程中使用像 Guy Gordon 这样的技巧（放置索引或任何东西来代替指针，或者如果它们小于 32 位，则直接放置值），它也是重量级的：我们需要构建一个列表等等......

因此，轻松快速地对结构数组进行排序的替代方法可能是使用 qsort C 运行时函数 来自 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';

完整示例 这里.

请注意，如果记录很大，直接对记录数组进行排序可能会很慢。在这种情况下，对指向记录的指针数组进行排序可能会更快（某种程度上类似于列表方法）。

Answer 6

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

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

另一个网站，但有 pascal 源代码http://www.dcc.uchile.cl/~rbaeza/handbook/sort_a.html

Answer 7

使用提出的排序算法之一 维基百科. 。Swap 函数应使用与数组元素类型相同的临时变量来交换数组元素。如果您希望具有相同 SortOrder 整数值的条目保持其最初的顺序，请使用稳定排序。

Answer 8

TStringList 有高效的排序方法。
如果你想排序使用 TStringList 对象与 Sorted 属性为 True。

笔记：为了提高速度，请在未排序的情况下添加对象 TStringList 最后将属性更改为 True。
笔记：对于按整数字段排序，请转换为字符串。
笔记：如果存在重复值，则此方法无效。

问候。

Answer 9

如果您有 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;

Answer 10

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

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;