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

Question

对于许多任务，我使用TList/TObjectList和TStringList(带有相关对象)，要么是原样使用，要么是作为更复杂结构的基础。虽然排序功能通常足够好，但我有时需要做一个稳定的排序，并且两个列表都使用快速排序。

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

Answer 1

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

你可以阅读当前的快速排序实现，并编写自己的稳定版本(例如合并排序或任何其他稳定版本)。

一些技巧:

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

Answer 2

这个问题相当老了，但我的回答是:我最近也需要这个，并改编了Julian Bucknall在《Delphi算法和数据结构》一书中找到的实现。TList, TObjectList和子类的实现。它可以与Delphi 2009到XE7以及可能其他版本一起使用:http://alexandrecmachado.blogspot.com.br/2015/02/merge-sort-for-delphi.html

Answer 3

来自类似的问题如何替换StringList。在Delphi中用稳定排序排序?我需要复制到这里，就像问题中提到的那样，非常简单的技巧。

您可以很容易地使快速排序行为稳定，只需在数据中添加初始顺序号进行排序，并在CustomSort比较函数中添加最后比较条件来比较这些初始顺序号。

简单，快速，智能。只需要一个额外的整数(或字节)，或者使用一些保留的存储，如TComponent。

在每个可排序项上标记(如果你排序TComponents)，并在它们上面进行一个初始化循环。

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;

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