mergesortutils.pas

用delphi实现的一些排序算法

{-----------------------------------------------------------------------------

  作者：hujp 2006.05.09
  备注：
  审核：

  Copyright (c) 1994-2006 GrandSoft Corporation
-----------------------------------------------------------------------------}

unit MergeSortUtils;

interface

uses
  Classes;

type
  TCompareFunc = function (Item1, Item2: Pointer): Integer;

  procedure MergeSort(AList: TList; AFirst: Integer; ALast: Integer;
    ACompareFunc: TCompareFunc; ATempList: PPointerList);
implementation

{-----------------------------------------------------------------------------
  作者：hujp 2006.05.09
  参数：AList:待排序列表; ACompareFunc:比较函数; ATempList:临时列表
  返回：
  功能：二路归并排序
-----------------------------------------------------------------------------}
procedure MergeSort(AList: TList; AFirst: Integer; ALast: Integer;
  ACompareFunc: TCompareFunc; ATempList: PPointerList);
var
  nMid: Integer;
  I, J, ToIndex: Integer;
  nFirstCount: Integer;
begin
  nMid := (AFirst + ALast) div 2;
  if AFirst < nMid then
    MergeSort(AList, AFirst, nMid, ACompareFunc, ATempList);
  if Succ(nMid) < ALast then
    MergeSort(AList, Succ(nMid), ALast, ACompareFunc, ATempList);
  //将前一半复制到临时表中
  nFirstCount := Succ(nMid - AFirst);
  Move(AList.List^[AFirst], ATempList^[0], nFirstCount * Sizeof(Pointer));

  //I为临时表的索引（表的前一半），J为表后一半的索引，ToIndex为元素将复制到的已归并表中的索引
  I := 0;
  J := Succ(nMid);
  ToIndex := AFirst;
  while (I < nFirstCount) and (J <= ALast) do
  begin
    if ACompareFunc(ATempList^[I], AList.List^[J]) <= 0 then
    begin
      AList.List^[ToIndex] := ATempList^[I];
      Inc(I);
    end
    else begin
      AList.List^[ToIndex] := AList.List^[J];
      Inc(J);
    end;
    Inc(ToIndex);
  end;
  if I < nFirstCount then
    Move(ATempList^[I], AList.List^[ToIndex], (nFirstCount - I) * Sizeof(Pointer));
end;

end.