delphi - 如何在 Delphi 中用稳定排序替换 StringList.Sort？

Question

我正在做一个简单的 StringList.sort，但 Delphi 使用的 QuickSort 不是稳定的排序，这意味着它可能会改变具有相同键的记录的相对顺序。

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

<小时/>

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

谢谢，迈克。

Answer 1

如果您尚未使用字符串列表的 Objects 属性，一个快速但肮脏的解决方案是将对象属性中的原始位置存储为整数。然后，您可以提供自己的稳定排序比较函数，该函数会考虑原始位置。您在自己的代码中所要做的就是在调用 CustomSort 之前迭代整个列表并分配对象属性:

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;