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

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而不是数组.它具有处理插入和删除以及保持秩序的方法.

如果您一次执行大量插入操作,则需要使用脏插入算法,其工作方式如下:

该列表带有一个关联的标志,一个名为的布尔值 Dirty.插入内容时,将其粘贴在列表的末尾,然后设置Dirty为True.当你从列表中读取时,首先检查Dirty标志,如果它的值是True,则对列表进行排序,设置 Dirty := False;然后执行读取.使用大量插入时,这比在插入时按列表顺序保持列表要快得多.

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

由于您的数据已经排序,因此您可以使用二进制搜索找到新值的正确位置.让Insert操作使用二进制搜索来确定新值应该去哪里,将其插入那里,并且列表保持排序顺序.

至于删除,您不必担心排序顺序.只需打电话Delete给你TList,如果它开始排序,删除一个项目将不会改变它.