排序数组的最佳方法。

Say I have an array of records which I want to sort based on one of the fields in the record. What's the best way to achieve this?

假设我有一个记录数组，我想根据记录中的一个字段进行排序。达到这一目标的最佳方式是什么?

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

var SomeVar : array of TExample;

10 个解决方案

#1

You can add pointers to the elements of the array to a TList, then call TList.Sort with a comparison function, and finally create a new array and copy the values out of the TList in the desired order.

可以将数组元素的指针添加到TList，然后调用TList。排序与一个比较函数，最后创建一个新的数组，并按照所需的顺序从TList中复制值。

However, if you're using the next version, D2009, there is a new collections library which can sort arrays. It takes an optional IComparer<TExample> implementation for custom sorting orders. Here it is in action for your specific case:

但是，如果您使用的是下一个版本D2009，则有一个新的集合库可以对数组进行排序。它接受一个可选的IComparer 实现，用于自定义排序顺序。这里是针对你的具体情况的行动:

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

#2

(I know this is a year later, but still useful stuff.)

(我知道这是一年后的事了，但仍然是有用的东西。)

Skamradt's suggestion to pad integer values assumes you are going to sort using a string compare. This would be slow. Calling format() for each insert, slower still. Instead, you want to do an integer compare.

Skamradt提出的填充整数值的建议假设您将使用一个字符串比较。这将是缓慢的。对每个插入调用format()，速度更慢。相反，您需要做一个整数比较。

You start with a record type:

你从记录类型开始:

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

You didn't state how the records were stored, or how you wanted to access them once sorted. So let's assume you put them in a Dynamic Array:

您没有说明记录是如何存储的，也没有说明您希望如何访问它们。假设你把它们放在一个动态数组中

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;

Now you want to sort this array by the integer value SortOrder. If what you want out is a TStringList (so you can use the ts.Find method) then you should add each string to the list and add the SortOrder as a pointer. Then sort on the pointer:

现在，您想按整数值排序这个数组。如果您想要的是一个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;

Note the trick of casting the Integer SortOrder into a TObject pointer, which is stored in the TStringList.Object property. (This depends upon the fact that Integer and Pointer are the same size.) Somewhere we must define a function to compare the TObject pointers:

请注意将整数排序顺序转换为一个TObject指针的技巧，该指针存储在TStringList中。对象属性。(这取决于整数和指针的大小相同。)在某些地方，我们必须定义一个函数来比较TObject指针:

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

Now, we can sort the tsList on .Object by calling .CustomSort instead of .Sort (which would sort on the string value.)

现在，我们可以通过调用. customsort而不是. sort(对字符串值进行排序)对. object上的tsList进行排序。

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

The TStringList is now sorted, so you can iterate over it from 0 to .Count-1 and read the strings in sorted order.

TStringList现在已被排序，因此您可以从0到. count -1对它进行迭代，并按排序后的顺序读取字符串。

But suppose you didn't want a TStringList, just an array in sorted order. Or the records contain more data than just the one string in this example, and your sort order is more complex. You can skip the step of adding every string, and just add the array index as Items in a TList. Do everything above the same way, except use a TList instead of TStringList:

但假设你不想要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;

Now that Mlist is sorted, use it as a lookup table to access the array in sorted order:

现在Mlist已排序，使用它作为查找表以按排序的顺序访问数组:

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

As i iterates over the TList, we get back the array indexes in sorted order. We just need to cast them back to integers, since the TList thinks they're pointers.

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

I like doing it this way, but you could also put real pointers to array elements in the TList by adding the Address of the array element instead of it's index. Then to use them you would cast them as pointers to TExample records. This is what Barry Kelly and CoolMagic said to do in their answers.

我喜欢这样做，但是您也可以通过添加数组元素的地址而不是索引来将真正的指针指向数组元素。然后要使用它们，您将它们转换为指向TExample记录的指针。这就是巴里·凯利和酷魔术在他们的回答中所说的。

#3

If your need sorted by string then use sorted TStringList and add record by TString.AddObject(string, Pointer(int_val)).

如果需要按字符串排序，则使用已排序的TStringList并按TString添加记录。AddObject(字符串指针(int_val))。

But If need sort by integer field and string - use TObjectList and after adding all records call TObjectList.Sort with necessary sorted functions as parameter.

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

#4

This all depends on the number of records you are sorting. If you are only sorting less than a few hundred then the other sort methods work fine, if you are going to be sorting more, then take a good look at the old trusty Turbo Power SysTools project. There is a very good sort algorithm included in the source. One that does a very good job sorting millions of records in a efficient manner.

这一切都取决于正在排序的记录的数量。如果排序少于几百种，那么其他的排序方法也可以，如果你想要进行更多的排序，那么请仔细看看以前值得信赖的涡轮动力系统项目。源代码中包含了一个很好的排序算法。一种高效地对数百万条记录进行排序的方法。

If you are going to use the tStringList method of sorting a list of records, make sure that your integer is padded to the right before inserting it into the list. You can use the format('%.10d',[rec.sortorder]) to right align to 10 digits for example.

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

#5

The quicksort algorithm is often used when fast sorting is required. Delphi is (Or was) using it for List.Sort for example. Delphi List can be used to sort anything, but it is an heavyweight container, which is supposed to look like an array of pointers on structures. It is heavyweight even if we use tricks like Guy Gordon in this thread (Putting index or anything in place of pointers, or putting directly values if they are smaller than 32 bits): we need to construct a list and so on...

当需要快速排序时，通常使用快速排序算法。Delphi正在(或曾经)使用它作为列表。例如。Delphi列表可以用来排序任何东西，但是它是一个重量级容器，它看起来像一个关于结构的指针数组。它是重量级的，即使我们在这个线程中使用Guy Gordon这样的技巧(放置索引或其他东西来代替指针，或者直接放置小于32位的值):我们需要构建一个列表，等等……

Consequently, an alternative to easily and fastly sort an array of struct might be to use qsort C runtime function from msvcrt.dll.

因此，可以使用msvcr .dll中的qsort C运行时函数，方便快捷地对结构数组进行排序。

Here is a declaration that might be good (Warning: code portable on windows only).

这里有一个很好的声明(警告:代码只能在windows上移植)。

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

Full example here.

完整的例子。

Notice that directly sorting the array of records can be slow if the records are big. In that case, sorting an array of pointer to the records can be faster (Somehow like List approach).

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

#6

With an array, I'd use either quicksort or possibly heapsort, and just change the comparison to use TExample.SortOrder, the swap part is still going to just act on the array and swap pointers. If the array is very large then you may want a linked list structure if there's a lot of insertion and deletion.

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

C based routines, there are several here http://www.yendor.com/programming/sort/

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

Another site, but has pascal source http://www.dcc.uchile.cl/~rbaeza/handbook/sort_a.html

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

#7

Use one of the sort alorithms propose by Wikipedia. The Swap function should swap array elements using a temporary variable of the same type as the array elements. Use a stable sort if you want entries with the same SortOrder integer value to stay in the order they were in the first place.

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

#8

TStringList have efficient Sort Method.
If you want Sort use a TStringList object with Sorted property to True.

TStringList具有高效的排序方法。如果您想要排序，请使用具有排序属性的TStringList对象。

NOTE: For more speed, add objects in a not Sorted TStringList and at the end change the property to True.
NOTE: For sort by integer Field, convert to String.
NOTE: If there are duplicate values, this method not is Valid.

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

Regards.

的问候。

#9

I created a very simple example that works correctly if the sort field is a string.

我创建了一个非常简单的示例，如果sort字段是字符串，那么该示例将正确地工作。

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;

#10

If you have Delphi XE2 or newer, you can try:

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

#1