排序数组的最佳方法

假设我有一系列记录,我想根据记录中的一个字段进行排序.实现这一目标的最佳方法是什么？

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

var SomeVar : array of TExample;

Barry Kelly.. 36

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

但是,如果您使用的是下一个版本D2009,则会有一个可以对数组进行排序的新集合库.它需要一个IComparer自定义排序顺序的可选实现.在这里,它针对您的具体情况:

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

解决问题是一回事.写一个优雅的解决方案(意思是"容易上眼")是另一回事.我不认为这段代码看起来不错或足够可读.我讨厌Delphi慢慢失去其可读性,否则没有理由不改用C#作为我的首选语言. (3认同)

这个解决方案很简洁,简洁,因为它重用了许多常用的代码并允许匿名函数内联编写,而不是强迫你创建一个虚函数声明,这样你就可以将它传递给这个函数.您可以自己重写所有这些代码并占用一两页或三页.或者你可以用五行来完成.我认为较长版本是否比较短版本更"可读",这有点争议. (3认同)

---

Guy Gordon.. 12

(我知道这是一年之后,但仍然有用.)

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中的Items.除了使用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在答案中所说的.

1> Barry Kelly..：

---

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

但是,如果您使用的是下一个版本D2009,则会有一个可以对数组进行排序的新集合库.它需要一个IComparer自定义排序顺序的可选实现.在这里,它针对您的具体情况:

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

---

解决问题是一回事.写一个优雅的解决方案(意思是"容易上眼")是另一回事.我不认为这段代码看起来不错或足够可读.我讨厌Delphi慢慢失去其可读性,否则没有理由不改用C#作为我的首选语言.

---

这个解决方案很简洁,简洁,因为它重用了许多常用的代码并允许匿名函数内联编写,而不是强迫你创建一个虚函数声明,这样你就可以将它传递给这个函数.您可以自己重写所有这些代码并占用一两页或三页.或者你可以用五行来完成.我认为较长版本是否比较短版本更"可读",这有点争议.

2> Guy Gordon..：

---

(我知道这是一年之后,但仍然有用.)

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中的Items.除了使用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在答案中所说的.