向 TList 和 TStringList 添加稳定排序的简单方法

Question

我将 TList/TObjectList 和 TStringList（带有关联对象）用于多种任务，或者按原样使用，或者作为更复杂结构的基础。虽然排序功能通常足够好，但有时我需要稳定 排序，两个列表都使用快速排序。

为 TList 和/或 TStringList 实现稳定排序的最简单方法是什么？我是否必须编写自己的排序例程，或者可以通过使用 TStringListSortCompare/TListSortCompare 的一些巧妙技巧来完成吗？

Answer 1

您必须编写自己的排序例程。

您可以阅读当前的 QuickSort 实现，并编写自己的稳定版本（例如合并排序或任何其他稳定变体< /a>）。

一些技巧：

• 如果您确定索引 < Count，您可以使用快速指针数组 (TList.List[])，而不是较慢的 Items[] 或 GetItem()：子方法调用和范围检查会减慢执行速度；
• 比较函数大多数时候是搜索的速度瓶颈——所以要小心这部分；
• 如果您需要速度，请在真实（例如随机）数据上使用真实的分析器 - 但在使其快速之前先使其正确；
• 从现有的排序实现开始；
• 为了最小化堆栈空间，您可以使用临时记录来存储并在递归调用之间共享变量。

Answer 2

这个问题相当老了，但这是我对未来读者的回答：
我最近也需要这个，并改编了 Julian Bucknall 所著的《The Tomes of Delphi Algorithms and Data Structures》一书中的实现。 TList、TObjectList 及其后代类的实现。它适用于 Delphi 2009 到 XE7 以及可能其他版本：
http://alexandrecmachado.blogspot.com.br/2015 /02/merge-sort-for-delphi.html

Answer 3

来自类似的问题 How Can I Replace StringList .在 Delphi 中使用稳定排序进行排序？，在 lkessler 的评论中链接到这里，我需要将问题中提到的非常简单的技巧复制到这里。

只需将初始订单号添加到要排序的数据中，并在 CustomSort 比较函数中添加最后一个比较条件来比较该初始订单号，即可轻松使快速排序表现稳定。

简单、快速、智能。每个可排序项仅花费一个额外的整数（或字节，或者如果对 TComponent 进行排序，则使用一些保留存储，如 TComponent.Tag），并对其进行一次初始化循环。

TObjectToSort = class
  ...
  Index: Integer;
end;

function MyStableSortComparer(List: TStringList; Index1, Index2: Integer): Integer;
var
  o1, o2: TObjectToSort; 
begin
  o1 := TObjectToSort(List.Objects[Index1]);
  o2 := TObjectToSort(List.Objects[Index2]);
  ...
  if Result = 0 then
    Result := o1.Index - o2.Index;
end;


for i := 0 to MyStrtingList.Count - 1 do
  TObjectToSort(MyStrtingList.Objects[i]).Index := i;
MyStrtingList.CustomSort(MyStableSortComparer);

Answer 4

对于任何使用泛型的人来说，这里是插入和合并排序的现成实现，这两种算法都是稳定的排序算法。

uses Generics.Defaults, Generics.Collections;

type
  TMySort = class
  public
    class procedure InsertionSort<T>(AArray: TArray<T>; FirstIndex, LastIndex: Integer; const AComparer: IComparer<T>); static;
    class procedure MergeSort<T>(AArray: TArray<T>; FirstIndex, LastIndex: Integer; const AComparer: IComparer<T>); static;
  end;

implementation

class procedure TMySort.InsertionSort<T>(AArray: TArray<T>; FirstIndex, LastIndex: Integer; const AComparer: IComparer<T>);
var
  UnsortedIdx, CompareIdx: Integer;
  AItem: T;
begin
  for UnsortedIdx := Succ(FirstIndex) to LastIndex do begin
    AItem := AArray[UnsortedIdx];
    CompareIdx := UnsortedIdx - 1;
    while (CompareIdx >= FirstIndex) and (AComparer.Compare(AItem, AArray[CompareIdx]) < 0) do begin
      AArray[CompareIdx + 1] := AArray[CompareIdx]; { shift the compared (bigger) item to the right }
      Dec(CompareIdx);
    end;
    AArray[CompareIdx + 1] := AItem;
  end;
end;

class procedure TMySort.MergeSort<T>(AArray: TArray<T>; FirstIndex, LastIndex: Integer; const AComparer: IComparer<T>);
const
  MinMergeSortLimit = 16;
var
  LeftLast, RightFirst: Integer;
  LeftIdx, RightIdx, SortedIdx: Integer;
  LeftCount: Integer;
  TmpLeftArray: TArray<T>;
begin
  if (LastIndex - FirstIndex) < MinMergeSortLimit then
    { sort small chunks with insertion sort (recursion ends here)}
    TMySort.InsertionSort<T>(AArray, FirstIndex, LastIndex, AComparer)
  else begin
    { MERGE SORT }
    { calculate the index for splitting the array in left and right halves }
    LeftLast := (FirstIndex + LastIndex) div 2;
    RightFirst := LeftLast + 1;
    { sort both halves of the array recursively }
    TMySort.MergeSort<T>(AArray, FirstIndex, LeftLast, AComparer);
    TMySort.MergeSort<T>(AArray, RightFirst, LastIndex, AComparer);
    { copy the first half of the array to a temporary array }
    LeftCount := LeftLast - FirstIndex + 1;
    TmpLeftArray := System.Copy(AArray, FirstIndex, LeftCount);
    { setup the loop variables }
    LeftIdx := 0;  { left array to merge -> moved to TmpLeftArray, starts at index 0 }
    RightIdx := RightFirst; { right array to merge -> second half of AArray }
    SortedIdx := FirstIndex - 1; { range of merged items }
    { merge item by item until one of the arrays is empty }
    while (LeftIdx < LeftCount) and (RightIdx <= LastIndex) do begin
      { get the smaller item from the next items in both arrays and move it
        each step will increase the sorted range by 1 and decrease the items still to merge by 1}
      Inc(SortedIdx);
      if AComparer.Compare(TmpLeftArray[LeftIdx], AArray[RightIdx]) <= 0 then begin
        AArray[SortedIdx] := TmpLeftArray[LeftIdx];
        Inc(LeftIdx);
      end else begin
        AArray[SortedIdx] := AArray[RightIdx];
        Inc(RightIdx);
      end;
    end;
    { copy the rest of the left array, if there is any}
    while (LeftIdx < LeftCount) do begin
      Inc(SortedIdx);
      AArray[SortedIdx] := TmpLeftArray[LeftIdx];
      Inc(LeftIdx);
    end;
    { any rest of the right array is already in place }
  end;
end;

该实现是针对数组进行的，也适用于 TList/TObjectList（因为它们的 Items 属性是一个数组）。

var
  AList: TList<T>;
  AComparer: IComparer<T>;
begin
  ...
  TMySort.MergeSort<T>(AList.List, 0, AList.Count-1, AComparer);
  ...
end;

除了稳定之外，根据我的经验，这种合并排序实现确实比内置快速排序表现出更好的性能（尽管它使用更多内存）。