logo标签列表

按多个字段对数组进行排序

arraysdelphisortingdelphi-xe7
3

我有多个数组，它们都以整数字段开头，从1到5个字段不等，这些像索引一样的字段需要按照从小到大的顺序排序：

    TArrayA = record
          Field1:integer;
          Field2:integer;
          Field3:integer;
          Field4:integer;
          Field5:integer;
          ... //other fields, strings, integers... up to 50 fields
        end;

    ArrayA:=array of TArrrayA;

目前我使用以下方法进行排序：

    // sort by Field1
    top:=Length(ArrayA);
      for counter := 0 to top do
        begin
          min := counter;
          for look := counter + 1 to top do
            if ArrayA[look].Field1 < ArrayA[min].Field1 then
              min := look;
          vTmpRecord := ArrayA[min];
          ArrayA[min] := ArrayA[counter];
          ArrayA[counter] := vTmpRecord;
        end;

   // now sort by Field2
    top:=Length(ArrayA);
      for counter := 0 to top do
        begin
          min := counter;
          for look := counter + 1 to top do
            if (ArrayA[look].Field1 = ArrayA[min].Field1) And 
               (ArrayA[look].Field2 < ArrayA[min].Field2) then
              min := look;
          vTmpRecord := ArrayA[min];
          ArrayA[min] := ArrayA[counter];
          ArrayA[counter] := vTmpRecord;
        end;

这个代码能够完成工作。但是当我需要对所有5个字段进行排序时，它有些慢，所以我只能一个字段一个字段地进行排序，需要对数组进行5次排序。是否有更好、更快的方法？

以下是一个例子：

procedure TForm1.Button8Click(Sender: TObject);
type
  TArrayA = record
    Field1: integer;
    Field2: integer;
    Field3: integer;
    Field4: integer;
    Field5: integer;
  end;
var
  ArrayA: array of TArrayA;
  vTmpRecord: TArrayA;
  top, counter, min, max, look: integer;
  i,t1,t2:integer;
begin

  SetLength(ArrayA,100000);
  for i := 0 to 99999 do
  begin
    ArrayA[i].Field1:=1+Random(100);
    ArrayA[i].Field2:=1+Random(100);
    ArrayA[i].Field3:=1+Random(100);
    ArrayA[i].Field4:=1+Random(100);
    ArrayA[i].Field5:=1+Random(100);
  end;


  t1:=GetTickCount;
  // sort by Field1
  top := Length(ArrayA);
  for counter := 0 to top do
  begin
    min := counter;
    for look := counter + 1 to top do
      if ArrayA[look].Field1 < ArrayA[min].Field1 then
        min := look;
    vTmpRecord := ArrayA[min];
    ArrayA[min] := ArrayA[counter];
    ArrayA[counter] := vTmpRecord;
  end;

  // sort by Field2
  top := Length(ArrayA);
  for counter := 0 to top do
  begin
    min := counter;
    for look := counter + 1 to top do
      if (ArrayA[look].Field1 = ArrayA[min].Field1) and
        (ArrayA[look].Field2 < ArrayA[min].Field2) then
        min := look;
    vTmpRecord := ArrayA[min];
    ArrayA[min] := ArrayA[counter];
    ArrayA[counter] := vTmpRecord;
  end;

  // sort by Field3
  top := Length(ArrayA);
  for counter := 0 to top do
  begin
    min := counter;
    for look := counter + 1 to top do
      if (ArrayA[look].Field1 = ArrayA[min].Field1) and (ArrayA[look].Field2 = ArrayA[min].Field2) and
        (ArrayA[look].Field3 < ArrayA[min].Field3) then
        min := look;
    vTmpRecord := ArrayA[min];
    ArrayA[min] := ArrayA[counter];
    ArrayA[counter] := vTmpRecord;
  end;

  // sort by Field4
  top := Length(ArrayA);
  for counter := 0 to top do
  begin
    min := counter;
    for look := counter + 1 to top do
      if (ArrayA[look].Field1 = ArrayA[min].Field1) and (ArrayA[look].Field2 = ArrayA[min].Field2) and (ArrayA[look].Field3 = ArrayA[min].Field3) and
        (ArrayA[look].Field4 < ArrayA[min].Field4) then
        min := look;
    vTmpRecord := ArrayA[min];
    ArrayA[min] := ArrayA[counter];
    ArrayA[counter] := vTmpRecord;
  end;

  // sort by Field5
  top := Length(ArrayA);
  for counter := 0 to top do
  begin
    min := counter;
    for look := counter + 1 to top do
      if (ArrayA[look].Field1 = ArrayA[min].Field1) and (ArrayA[look].Field2 = ArrayA[min].Field2) and (ArrayA[look].Field3 = ArrayA[min].Field3) and (ArrayA[look].Field4 = ArrayA[min].Field4) and
        (ArrayA[look].Field5 < ArrayA[min].Field5) then
        min := look;
    vTmpRecord := ArrayA[min];
    ArrayA[min] := ArrayA[counter];
    ArrayA[counter] := vTmpRecord;
  end;

  t2:=GetTickCount;
  Button8.Caption:=IntToStr(t2-t1);
end;
参见：如何使用多个比较器在TObjectList<>中实现类似Excel的按A排序，然后按B排序。 - Rob Kennedy
2个回答
4
您可以使用内置的快速排序方法来使用自定义比较器对数组进行排序：
uses
  System.Math,
  System.Generics.Defaults,
  System.Generics.Collections;

  TArray.Sort<TArrayA>(ArrayA, TComparer<TArrayA>.Construct( function(const Left, Right: TArrayA): Integer
  begin
    if Left.Field1 = Right.Field1 then
      begin
        if Left.Field2 = Right.Field2 then
          begin
            Result := CompareValue(Left.Field3, Right.Field3);
          end
        else Result := CompareValue(Left.Field2, Right.Field2);
      end
    else Result := CompareValue(Left.Field1, Right.Field1);
  end
  ));

我只添加了前三个字段的代码，但您可以了解如何为更多字段构建自己的比较器。

1
阅读有关快速排序和冒泡排序以及它们的渐近行为的内容。尽量避免使用此处实现的比较器，因为它充满了重复。选择使用迭代的比较器。 - David Heffernan
@DavidHeffernan 同意，这里的比较器有些重复。但是，我认为它很好地说明了如何构建自己的比较器。特别是，如果您必须针对不同字段使用不同的比较算法（当然，在此示例代码中并非如此）。 - Dalija Prasnikar
1
至少您应该使用早期返回以避免深度嵌套缩进，并避免使用容易发生算术溢出的减法。但是迭代更好。不要重复自己。 - David Heffernan
我非常强烈地不同意那个观点。无论如何，我就不再多说了，我的观点已经足够清楚了。 - David Heffernan
谢谢@DalijaPrasnikar，但我会选择David的解决方案，因为我需要转换150多个排序部分，他的解决方案应该有助于优化未来的排序。 - Mike Torrettinni
显示剩余4条评论
2
你需要做的最重要的事情是将排序算法与数据分离开来。这样，你就可以编写或使用单个排序算法，并将其应用于不同的数据。
经典的方法是使用比较排序。这些排序算法需要一个比较函数，该函数比较两个项目并返回负整数表示小于，正整数表示大于，等于零表示相等。
因此，让我们从为你的数据演示这样的比较函数开始。像你这样存储多个字段使得编写通用比较器变得困难，最好将字段放入数组中。一旦你这样做了，你就可以使用迭代按字典顺序进行比较，如下所示：
function CompareIntegerArray(const lhs, rhs: array of Integer): Integer;
var
  i: Integer;
begin
  Assert(Length(lhs) = Length(rhs));
  for i := low(lhs) to high(lhs) do
    if lhs[i] < rhs[i] then
      exit(-1)
    else if lhs[i] > rhs[i] then
      exit(1);

  exit(0);
end;

使用字典序排序时，我们首先比较主要字段。如果它们不同，我们就得到了答案，否则我们继续比较次要字段，以此类推。这种算法非常适合迭代，正如上面所示。

这克服了你的方法中一个重大的弱点，即只需对数组进行一次排序。

一旦您有了比较函数，您需要将其包装在一个外部比较函数中，该函数从记录字段中提取数据并填充数组。可能是这样的：

type
  TMyArray = array [1..5] of Integer;

function GetMyArray(const Value: TArrayA): TMyArray;
begin
  Result[1] := Value.Field1;
  Result[2] := Value.Field2;
  ....
end;

function MyCompare(const lhs, rhs: TArrayA): Integer;
begin
  Result := CompareIntegerArray(
    GetMyArray(lhs),
    GetMyArray(rhs)
  );
end;

现在，如承诺的那样，您可以将此比较函数与类似于Generics.Collections中的TArray.Sort<T>这样的通用排序一起使用。 这是Quicksort的实现，平均复杂度为O（n log n）的比较排序算法。这通常会比O（n2）bubble sort产生巨大的好处。
如果您能用实际数组替换记录，则生活将变得更简单。 另一个可能有用的选项是向记录添加一个返回整数数组以供词典比较函数使用的方法。
回顾一下：
  1. 分离数据、比较和排序以便于重用和清晰度。
  2. 使用数组使词典比较可以通过循环来实现。
  3. 使用高效的排序算法，例如Quicksort。
你的建议很有趣，看起来它是有效的。所以，我就像这样设置它并且它可以工作：TArray.Sort<TArrayA>(ArrayA, TComparer<TArrayA>.Construct( function(const Left, Right: TArrayA): Integer begin Result:=MyCompare(Left,Right); end ));。如果我想要对不同的数组进行排序，比如TArrayA2的数组，我只需要简单地复制函数GetMyArrayA2(const Value: TArrayA2): TMyArray;和function MyCompareA2(const lhs, rhs: TArrayA2): Integer;，并在TArray.Sort中调用这个新的MyCompareA2，对吗？你的例子比Dalija的慢一点，大约是170ms对120ms。 - Mike Torrettinni
1
你在比较器中增加了不必要的额外间接层。你可以直接将 MyCompare 传递给 Construct。或者，你可以将 MyCompare 的主体移动到一个匿名方法中，然后将其传递给 Construct。我更关心传达概念而不是优化性能。 - David Heffernan
谢谢，这似乎是我可以在整个应用程序中应用的解决方案——大约有150个排序部分。 - Mike Torrettinni
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接