arrays - 添加/删除单元格时保持数组排序的最佳方法

Question

使用的 Delphi 版本:2007

你好，

我有一个 Tecord 数组

TInfo = Record
 Name : String;
 Price : Integer;
end;

var Infos : Array of Tinfo;

我正在寻找一种对我的 Infos 数组进行排序的方法，并找到了我认为是一种聪明的方法。基本上，我有一个 TList，其中添加了指向数组每个单元格的指针；然后，我使用自定义排序功能对它们进行排序。然后，此 TList 用于在 TListView 中显示排序的单元格，并将 OwnerData 设置为 true。

var SortedInfo : TList;

...

function CompareInfo(Item1, Item2: Integer): Integer;
var
 i, j : integer;
begin
 i := Integer(Item1);
 j := Integer(Item2);
 Result := CompareText(Infos[i].Name, Infos[j].Name);
end;

...

for I := 0 to Length(Infos) - 1 do SortedInfo.Add(Pointer(I));
SortedInfo.Sort(@CompareInfo);

...

procedure InfoHandlerData(Sender: TObject; Item: TListItem);
begin
 Item.Caption := Infos[Integer(SortedInfo[Item.Index])].Name;
 Item.SubItems.Add(IntToStr(Infos[Integer(SortedInfo[Item.Index])].Price);
end;

现在，我希望能够添加和删除单元格，同时保持指针排序。现在，这是我的问题。

1. 当我添加单元格时，我必须通过调用 SortedInfo.Sort(@CompareInfo); 来重新调用整个指针列表
2. 当我删除单元格时，我必须清理 TList、重建指针列表并再次对它们进行排序。

现在，我没有大量的单元，因此不存在性能问题。但是，当我删除单元格时重建指针并在每次数组更改时对所有指针进行排序对我来说似乎是错误的。如果我的问题看起来很愚蠢，我很抱歉，但我正在努力学习。

有没有正确的方法来保持我的数组排序？我不确定我应该如何“单独”对新单元格进行排序，或者当单元格被删除时我应该如何保持指针有效......

Answer 1

根据使用情况，有两种方法可以处理此问题。但首先，您可能应该使用 TList 而不是数组。它具有处理插入和删除以及保持事物有序的方法。

如果您一次执行大量插入，则需要使用脏插入算法，其工作原理如下:

The list comes with an associated flag, a boolean value called Dirty. When you insert something, stick it on the end of the list, and set Dirty to True. When you go to read from the list, first check the Dirty flag, and if its value is True, sort the list, set Dirty := False; and then do the read. With a lot of inserts, this is much faster than keeping the list in sorted order as you insert.

但是，如果您不太可能一次执行多次插入，则按排序顺序维护列表会更便宜。不过，您不需要每次都调用 Sort 来做到这一点。你这样做:

Because your data is already sorted, you can find the correct position for a new value by using a binary search. Have the Insert operation use a binary search to determine where the new value should go, insert it there, and your list remains in sorted order.

对于删除，您不必担心排序顺序。只需在 TList 上调用 Delete 即可，如果它开始已排序，则删除项目不会改变这一点。