如何在Delphi中使用稳定排序替换StringList.So...

codeday· 2019-11-11
本文来自 codeday ,作者 codeday
我正在做一个简单的StringList.sort,但是Delphi使用的QuickSort不是一个稳定的排序,这意味着它可能会改变具有相同键的记录的相对顺序.

我需要使用稳定的排序.对我来说,实现这个最简单的方法是什么?

Mike W的答案可能是最简单的方法,无需进行太多的代码更改.

谢谢,迈克.

最佳答案
如果您尚未使用字符串列表的Objects属性,则快速而肮脏的解决方案是将对象属性中的原始位置存储为整数.然后,您可以提供自己的稳定排序比较功能,该功能将原始位置考虑在内.您在自己的代码中所要做的就是在调用CustomSort之前迭代整个列表分配objects属性:

function StableSortCompare(List: TStringList; Index1, Index2: Integer): Integer;
begin
  result := CompareStr(List[Index1], List[Index2]);
  if result = 0 then result := integer(List.Objects[Index1]) - integer(List.Objects[Index2]);
end;

procedure TSortTestForm.SortButtonClick(Sender: TObject);
var
  SL : TStringList;
  i : integer;
begin
  SL := TStringList.Create;
  try
    SL.AddObject('One', pointer(0));
    SL.AddObject('One', pointer(1));
    SL.AddObject('One', pointer(2));
    SL.AddObject('Two', pointer(3));
    SL.AddObject('Two', pointer(4));
    SL.AddObject('One', pointer(5));
    SL.AddObject('One', pointer(6));
    SL.AddObject('One', pointer(7));
    // SL.Sort; // Try instead of custom sort to see difference
    SL.CustomSort(StableSortCompare);
    for i := 0 to SL.Count-1 do begin
      Memo1.Lines.Add(Format('Text: %s Orig Pos: %d', [SL[i], integer(SL.Objects[i])]));
    end;
  finally
    SL.Free;
  end;
end;