logo标签列表

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

delphilistsortingstable-sort
10

我经常使用 TList/TObjectList 和 TStringList（带有相关对象），用于各种任务，有时直接使用它们，有时作为更复杂结构的基础。虽然排序功能通常足够好，但我有时需要进行稳定排序，而这两个列表都使用快速排序。

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

1
参见：https://dev59.com/MmDVa4cB1Zd3GeqPd3w3 - lkessler
4个回答
5

你需要编写自己的排序程序。

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

一些技巧：

  • 如果你确定索引小于Count，可以使用快速指针数组(TList.List[])，而不是较慢的Items[]或GetItem()：子方法调用和范围检查会减慢执行速度；
  • 比较函数大部分时间是搜索速度瓶颈 - 所以要注意这个部分；
  • 如果你需要速度，请使用真实数据上的真正分析器 - 但在加速之前，请确保正确性；
  • 从现有的排序实现开始；
  • 为了最小化堆栈空间，可以使用临时记录来存储和共享递归调用之间的变量。
我本以为我必须自己写，但最终还是不得不问别人。我希望有一些“魔法”技巧 :-) 说起来，Borland/Embarcadero为什么没有让TList.Sort稳定呢？虽然我不是专家，但我相信有一些排序算法与快速排序的性能相同，而且内存使用率相当适中。唉，算了。 - Svein Bringsli
据所有书籍所述，快速排序是一种众所周知的排序算法，同时具有快速、易于编码和调试以及低内存使用的特点。稳定变体（如归并或插入排序）更加复杂，且不能提供更好的性能。在VCL中进行排序不需要稳定性，因此快速排序是通用排序实现的最佳选择。 - Arnaud Bouchez
3

这个问题很久远了，但我为未来读者提供我的答案：最近我也需要这个，并采用了在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

我写了一些单元测试，不幸的是排序似乎并不完全稳定 :( 我会在你的博客上发布这个测试。 - dan-gph
1
原始代码中存在一个错误，感谢您的发现和通知。代码已经修复，是的，我将在生产中使用它。 以下是有关问题和解决方案的信息： http://alexandrecmachado.blogspot.com.br/2015/03/merge-sort-for-delphi-revisited.html - Alexandre M
不鼓励仅提供链接的答案。 - David Heffernan
@DavidHeffernan 我觉得你是起床没睡醒吧？你是花时间查看每个用户的所有问题，只要他们指出了你答案中不完整的信息，还是只有在我的情况下？哈哈 - Alexandre M
不如专注于我的评论内容，而不是将其个人化。 - David Heffernan
显示剩余4条评论
0

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

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;

除了稳定性之外，在我的经验中，这个归并排序实现比内置的快速排序表现更好（尽管它使用更多的内存）。
0

从类似问题在Delphi中如何用稳定排序替换StringList.Sort？，由lkessler在评论中链接到这里，我需要将问题中提到的非常简单的技巧复制到这里。

你可以通过将初始顺序号添加到要排序的数据中，并在CustomSort比较函数中添加最后的比较条件来使快速排序具有稳定性。

简单、快速、聪明。每个可排序项只需增加一个额外的整数（或字节，或使用一些保留存储器，如TComponent.Tag，如果您对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);
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接