Đối với bất kỳ ai sử dụng generics ở đây là việc triển khai sẵn sàng chèn và sắp xếp hợp nhất, cả hai thuật toán phân loại ổn định.
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;
Việc triển khai cũng được thực hiện cho các mảng và áp dụng cho TList/TObjectList (vì thuộc tính Hạng mục của chúng là một mảng).
var
AList: TList<T>;
AComparer: IComparer<T>;
begin
...
TMySort.MergeSort<T>(AList.List, 0, AList.Count-1, AComparer);
...
end;
Bên cạnh việc ổn định, theo kinh nghiệm của tôi, sắp xếp hợp nhất thực hiện điều này cho thấy hiệu suất tốt hơn so với xây dựng trong sắp xếp nhanh chóng (mặc dù nó sử dụng bộ nhớ nhiều hơn).
Xem thêm: http://stackoverflow.com/questions/9303488/how-can-i-replace-stringlist-sort-with-a-stable-sort-in-delphi – lkessler