Как заменить StringList.Sort на «Стабильная сортировка» в Delphi? - PullRequest
Новая
       54

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

3 голосов
/ 16 февраля 2012

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

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

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

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

1 Ответ

11 голосов
/ 16 февраля 2012

Если вы еще не используете свойство 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;
...