最佳的数组排序方法

Question

假设我有一个记录数组，我想根据其中一个字段对其进行排序。如何实现最佳效果？

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

var SomeVar : array of TExample;

- Marius

---

刚刚完成了这个练习，发现最好的方法是编写自己的代码。我认为任何答案都不应该被推荐为“最佳”。 - Sam

明白了。也许您可以添加一个包含解决问题的答案？ - Marius

《Delphi算法与数据结构大全》一书中有一些很好的信息，作者是Julian Bucknall。 - Richard A

在《Delphi算法和数据结构宝典》中有一些很好的信息。（在这里，以及其他地方：http://blog.boyet.com/blog/blog/tomes-of-delphi-algorithms-and-data-structures-kindle-edition/） - Richard A

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));

- Barry Kelly

---

请注意，在D2009编译器中，泛型存在多个问题，因此使用集合库永远不是一个好选择（因为会出现虚假的编译器内部错误和代码生成错误）。 在Delphi XE中，这些问题大多已经得到解决，但是使用泛型版本将会导致性能下降（并且您可能会失去一些代码清晰度/可调试性）。 - Eric Grange

解决问题是一回事，编写简洁易读的解决方案是另一回事。我认为这段代码看起来不好，也不够易读。如果 Delphi 逐渐失去了可读性，我会很遗憾，因为这将成为我放弃它，转而使用 C# 的一个更少的理由。 - Sam

这个解决方案之所以紧凑简洁，是因为它重复利用了很多常见的代码，并允许内联编写匿名函数，而不是强制你创建一个虚拟函数声明，以便将其传递给这个函数。你可以自己重新编写所有这些代码，需要一页、两页或三页。或者你可以用五行代码搞定。我认为更长的版本是否比更短的版本更“可读”还有一些争议。 - jep

@jep 问题的一部分在于匿名函数语法太冗长了。在另一个函数中放置整个函数只会使代码变得更加难以阅读。其次，如果我们有lambda表达式，特别是如果我们的排序使用键而不是自定义比较函数，那么整个操作将只需要一行代码。例如，在Python中，上面的整个排序操作将是sorted(someVar, key=lambda x: x.SortOrder)! Python不允许内联大于一行lambda的函数，因为这会导致代码难以阅读。我们真的需要lambda和键排序。 - alcalde

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;

请注意，将整数SortOrder转换为TObject指针的技巧，并将其存储在TStringList.Object属性中。（这取决于整数和指针具有相同的大小。）我们必须定义一个比较TObject指针的函数：

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

现在，我们可以通过调用.CustomSort而不是.Sort（它会按字符串值排序）来按.Object对tsList进行排序。

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

现在已经排序，因此您可以从0到.Count-1迭代它，并按排序顺序读取字符串。 <但是假设您不想要一个TStringList，只需要一个按排序顺序排列的数组。或者记录包含更多数据，而您的排序顺序更复杂。您可以跳过添加每个字符串的步骤，只需将数组索引作为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在他们的答案中建议的方法。

- Guy Gordon

---

看起来只是晚了一天 :) - Wouter van Nifterick

Answer 3

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

但是，如果需要按整数字段和字符串排序，则使用TObjectList，在添加所有记录后调用TObjectList.Sort并将必要的排序函数作为参数传递。

- CoolMagic

Answer 4

快速排序算法通常用于需要快速排序的情况。例如，Delphi在List.Sort中使用它。 Delphi List可用于对任何内容进行排序，但它是一个重量级容器，看起来像是一个结构体指针数组。即使我们像Guy Gordon在这个线程中使用技巧（将索引或任何东西放在指针的位置，或者直接放置小于32位的值），它仍然很重：我们需要构建一个列表等等...

因此，一个替代方案是使用msvcrt.dll中的qsort C运行时函数轻松快速地对结构体数组进行排序。

以下是一个可能很好的声明（警告：代码仅在Windows上可移植）。

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

完整示例在这里。

请注意，如果记录很大，则直接对记录数组进行排序可能会很慢。在这种情况下，对指向记录的指针数组进行排序可能会更快（有点类似 List 方法）。

- rt15

Answer 5

这完全取决于您要排序的记录数。如果只需要对少量记录进行排序，则其他排序方法可以正常工作；如果要对更多记录进行排序，则应仔细查看老牌 Turbo Power SysTools 项目。该项目包含了一个非常好的排序算法，可以以高效的方式对数百万条记录进行排序。

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

- skamradt

Answer 6

使用数组时，我会使用 quicksort 或者可能是 heapsort，然后只需更改比较方式为 TExample.SortOrder，交换部分仍然会作用于数组并交换指针。如果数组非常大，则可能需要链表结构，如果有大量插入和删除。

C语言的例程，可以在这里找到几个
http://www.yendor.com/programming/sort/

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

- ddowns

Answer 7

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

- Jacek Krawczyk

Answer 8

TStringList 有高效的排序方法。
如果你想要排序，请使用一个 TStringList 对象，并将 Sorted 属性设置为 True。

注意：为了提高速度，可以在未排序的 TStringList 中添加对象，最后再将属性更改为 True。
注意：如果要按整数字段排序，请先转换为字符串。
注意：如果存在重复值，则此方法无效。

祝好。

- Neftal&#237;

Answer 9

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

- malach

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;

- David Miró