Delphi泛型：TArray.Sort

Question

我刚开始接触这个技术，还有很多需要学习。

PNode = ^TNode;

TNode = record
  Obstacle : boolean;
  Visited : boolean;
  GCost : double; // Distance from Starting Node
  HCost : double; // Distance from Target Node
  x : integer;
  y : integer;
  vecNeighBour : array of PNode;
  Parent : PNode;
end;

在FormShow事件中，我填充了该数组：

 SetLength(Node,4,4);

 Image1.Height:=Length(Node)*50;
 Image1.Width:=Length(Node)*50;

 for x := Low(Node) to High(Node) do
   for y := Low(Node) to High(Node) do
      begin
        Node[x,y].Obstacle:=false;
        Node[x,y].Visited:=false;
        Node[x,y].GCost:=infinity;
        Node[x,y].HCost:=infinity;
        Node[x,y].x:=x;
        Node[x,y].y:=y;
      end;

现在我想按照 HCost 对这个数组进行排序，所以我尝试了以下代码。

  TArray.Sort<TNode>(Node , TComparer<TNode>.Construct(
  function(const Left, Right: TNode): double
  begin
    if Left.HCost > Right.HCost then
      Result:=Left.HCost
    else
      Result:=Right.HCost;
  end));

我在这方面的知识严重不足。我从Delphi中得到一个错误提示：

"Incompatible types: 'System.Generics.Defaults.TComparison'和'Procedure'"

我做错了什么呢？

- user1937012

---

请添加一个 [MCVE]。我不确定上下文。 - Dsm

Answer 1

比较函数必须返回一个整数值。它的定义如下：

type
  TComparison<T> = reference to function(const Left, Right: T): Integer;

你的函数返回了错误的类型。

function CompareDoubleInc(Item1, Item2: Double): Integer;
begin
  if Item1=Item2 then begin
    Result := 0;
  end else if Item1<Item2 then begin
    Result := -1
  end else begin
    Result := 1;
  end;
end;

....

TArray.Sort<TNode>(
  Node, 
  TComparer<TNode>.Construct(
    function(const Left, Right: TNode): Integer
    begin
      Result := CompareDoubleInc(Left.HCost, Right.HCost);
    end
  )
);

如果您想让它更简单，您可以委托给默认的双重比较器:

TArray.Sort<TNode>(
  Node, 
  TComparer<TNode>.Construct(
    function(const Left, Right: TNode): Integer
    begin
      Result := TComparer<Double>.Default.Compare(Left.HCost, Right.HCost);
    end
  )
);

- ventiseis

---

它不能处理第一个大于0的数字！CompareValue(0.0, NextDoubleGreater(0.0)) = 0。并且在排序比较函数中指定epsilon确实行不通。它们需要是等价关系。很难像那样写它们，当然CompareValue不符合要求。不，这不是另一个讨论。就在这里，就在现在。我修复了代码。 - David Heffernan

关于我所说的排序比较函数，考虑这三个值，在 CompareValue 下面。0、1e-10 和 1e-20。因此认为0和1e-10是不同的。然后认为1e-10和1e-20是不同的。但是0和1e-20被认为是相等的。当应用于比较排序算法时，这种方式会导致运行时错误、无限循环等问题。 - David Heffernan

@DavidHeffernan 为了避免无限循环，排序算法的主要点是比较函数对于相同的两个值始终返回相同的结果，而不是比较的准确性 - 但是无论如何，CompareValue() 不应该在排序中使用（而且它比您手动编写的代码慢得多）。 - Arnaud Bouchez

@ArnaudBouchez 不仅需要为两个值始终返回相同的结果，还需要实现一个完全顺序。这是更强的要求。 - David Heffernan

@DavidHeffernan 我不这么认为：快速排序允许存在多个相等的值，排序后的顺序会改变，但不会出现循环。唯一的要求是比较函数对于两个值返回的结果无论顺序如何都相同（即comp(a,b)=comp(b,a)始终成立）。 - Arnaud Bouchez