Как заменить StringList.Sort на "Стабильная сортировка" в Delphi?

Question

Я делаю простой StringList.sort, но Delphi использует QuickSort, который не является стабильной сортировкой, то есть он может изменить относительный порядок записей с равными ключами.

Мне нужно использовать стабильную сортировку. Что бы мне было проще всего реализовать это?

---

Ответ Майка У может быть самым простым способом сделать это без необходимости слишком большого изменения кода.

Спасибо, Майк.

Answer 1

Если вы еще не используете свойство Objects списка строк, быстрое и грязное решение - сохранить исходную позицию в свойстве objects как целое число. Затем вы можете предоставить свою собственную стабильную функцию сравнения сортировки, которая учитывает исходную позицию. Все, что вам нужно сделать в своем собственном коде, - это выполнить итерацию всего списка, назначая свойство 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;