排序算法总结

在工作中，用到了排序。顺便总结了一下。以下排序的各算法，我都验证无误。

包含冒泡排序、摇动排序、梳子排序、标准插入排序、优化的插入排序、

希尔排序、标准归并排序、优化的归并排序、

标准快速排序、无递归的快速排序、随机的快速排序、中间值的快速排序、

堆排序。

unitunit2;

interface

//冒泡排序
procedureBubbleSort(varabc:arrayofInteger);

//摇动排序
procedureShakerSort(varabc:arrayofInteger);

//梳子排序
procedureCombSort(varabc:arrayofInteger);

//选择排序
procedureSelectionSort(varabc:arrayofInteger);

//标准插入排序
procedureInsertionSortStd(varabc:arrayofInteger);

//优化的插入排序
procedureInsertionSort(varabc:arrayofInteger);

//希尔排序
procedureShellSort(varabc:arrayofInteger);

//标准归并排序
procedureMergeSortStd(varabc:arrayofInteger);

//优化的归并排序
procedureMergeSort(varabc:arrayofInteger);

//标准快速排序
procedureQuickSortStd(varabc:arrayofInteger);

//无递归的快速排序
procedureQuickSortNoRecurse(varabc:arrayofInteger);

//随机的快速排序
procedureQuickSortRandom(varabc:arrayofInteger);

//中间值的快速排序
procedureQuickSortMedian(varabc:arrayofInteger);

//优化的插入快速排序
procedureQuickSort(varabc:arrayofInteger);

//堆排序
procedureHeapSort(varabc:arrayofInteger);

implementation

//冒泡排序
procedureBubbleSort(varabc:arrayofInteger);
var
i,j:Integer;
Temp:Integer;
Done:boolean;
begin
fori:=0toHigh(abc)do
begin
Done:=true;
forj:=High(abc)+1downto0do
ifabc[j]<abc[j-1]then
begin
Temp:=abc[j];
abc[j]:=abc[j-1];
abc[j-1]:=Temp;
Done:=false;
end;
ifDonethen
Exit;
end;
end;

//梳子排序
procedureCombSort(varabc:arrayofInteger);
var
i,j:Integer;
Temp:Integer;
Done:boolean;
Gap:Integer;
begin
Gap:=High(abc);
repeat
Done:=true;
Gap:=(longint(Gap)*10)div13;
if(Gap<1)then
Gap:=1
elseif(Gap=9)or(Gap=10)then
Gap:=11;
fori:=0to(High(abc)-Gap)do
begin
j:=i+Gap;
ifabc[j]<abc[i]then
begin
Temp:=abc[j];
abc[j]:=abc[i];
abc[i]:=Temp;
Done:=false;
end;
end;
untilDoneand(Gap=1);
end;

//标准插入排序
procedureInsertionSortStd(varabc:arrayofInteger);
var
i,j:Integer;
Temp:Integer;
begin
fori:=0toHigh(abc)do
begin
Temp:=abc[i];
j:=i;
while(j>0)and(Temp<abc[j-1])do
begin
abc[j]:=abc[j-1];
dec(j);
end;
abc[j]:=Temp;
end;
end;

//优化的插入排序
procedureInsertionSort(varabc:arrayofInteger);
var
i,j:Integer;
IndexOfMin:Integer;
Temp:Integer;
begin
IndexOfMin:=0;
fori:=0toHigh(abc)do
ifabc[i]<abc[IndexOfMin]then
IndexOfMin:=i;
if(0<>IndexOfMin)then
begin
Temp:=abc[0];
abc[0]:=abc[IndexOfMin];
abc[IndexOfMin]:=Temp;
end;
fori:=0+2toHigh(abc)do
begin
Temp:=abc[i];
j:=i;
whileTemp<abc[j-1]do
begin
abc[j]:=abc[j-1];
dec(j);
end;
abc[j]:=Temp;
end;
end;

//选择排序
procedureSelectionSort(varabc:arrayofInteger);
var
i,j:Integer;
IndexOfMin:Integer;
Temp:Integer;
begin
fori:=0toHigh(abc)do
begin
IndexOfMin:=i;
forj:=itoHigh(abc)+1do
ifabc[j]<abc[IndexOfMin]then
IndexOfMin:=j;
Temp:=abc[i];
abc[i]:=abc[IndexOfMin];
abc[IndexOfMin]:=Temp;
end;
end;

//摇动排序
procedureShakerSort(varabc:arrayofInteger);
var
i:Integer;
Temp:Integer;
iMin,iMax:Integer;
begin
iMin:=0;
iMax:=High(abc)-Low(abc)+1;

while(iMin<iMax)do
begin
fori:=iMaxdownto0do
ifabc[i]<abc[i-1]then
begin
Temp:=abc[i];
abc[i]:=abc[i-1];
abc[i-1]:=Temp;
end;
inc(iMin);
fori:=0toiMaxdo
ifabc[i]<abc[i-1]then
begin
Temp:=abc[i];
abc[i]:=abc[i-1];
abc[i-1]:=Temp;
end;
dec(iMax);
end;
end;

//希尔排序
procedureShellSort(varabc:arrayofInteger);
var
i,j:Integer;
h:Integer;
Temp:Integer;
Ninth:Integer;
begin
h:=1;
Ninth:=High(abc)div9;
while(h<=Ninth)do
h:=(h*3)+1;
while(h>0)do
begin
fori:=htoHigh(abc)do
begin
Temp:=abc[i];
j:=i;
while(j>=(0+h))and(Temp<abc[j-h])do
begin
abc[j]:=abc[j-h];
dec(j,h);
end;
abc[j]:=Temp;
end;
h:=hdiv3;
end;
end;

//标准归并排序
procedureMergeSortStd(varabc:arrayofInteger);
procedureMSS(varabc:arrayofInteger;aFirst:Integer;aLast:Integer;aTempList:arrayofInteger);
var
Mid:Integer;
i,j:Integer;
ToInx:Integer;
FirstCount:Integer;
begin
Mid:=(aFirst+aLast)div2;
if(aFirst<Mid)then
MSS(abc,aFirst,Mid,aTempList);
if(succ(Mid)<aLast)then
MSS(abc,succ(Mid),aLast,aTempList);
FirstCount:=succ(Mid-aFirst);
Move(abc[aFirst],aTempList[0],FirstCount*sizeof(pointer));
i:=0;
j:=succ(Mid);
ToInx:=aFirst;
while(i<FirstCount)and(j<=aLast)do
begin
if(aTempList[i]<=abc[j])then
begin
abc[ToInx]:=aTempList[i];
inc(i);
end
else
begin
abc[ToInx]:=abc[j];
inc(j);
end;
inc(ToInx);
end;
if(i<FirstCount)then
Move(aTempList[i],abc[ToInx],(FirstCount-i)*sizeof(pointer));
end;

var
TempList:arrayofInteger;
begin
if(0<High(abc))then
begin
SetLength(TempList,High(abc)div2);
MSS(abc,0,High(abc),TempList);
end;
end;

//优化的归并排序
procedureMergeSort(varabc:arrayofInteger);
const
MSCutOff=15;

procedureMSInsertionSort(varabc:arrayofInteger;aFirst:Integer;aLast:Integer);
var
i,j:Integer;
IndexOfMin:Integer;
Temp:Integer;
begin
IndexOfMin:=aFirst;
fori:=succ(aFirst)toaLastdo
ifabc[i]<abc[IndexOfMin]then
IndexOfMin:=i;
if(aFirst<>IndexOfMin)then
begin
Temp:=abc[aFirst];
abc[aFirst]:=abc[IndexOfMin];
abc[IndexOfMin]:=Temp;
end;
fori:=aFirst+2toaLastdo
begin
Temp:=abc[i];
j:=i;
whileTemp<abc[j-1]do
begin
abc[j]:=abc[j-1];
dec(j);
end;
abc[j]:=Temp;
end;
end;

procedureMS(varabc:arrayofInteger;aFirst:Integer;aLast:Integer;aTempList:arrayofInteger);
var
Mid:Integer;
i,j:Integer;
ToInx:Integer;
FirstCount:Integer;
begin
Mid:=(aFirst+aLast)div2;
if(aFirst<Mid)then
if(Mid-aFirst)<=MSCutOffthen
MSInsertionSort(abc,aFirst,Mid)
else
MS(abc,aFirst,Mid,aTempList);
if(succ(Mid)<aLast)then
if(aLast-succ(Mid))<=MSCutOffthen
MSInsertionSort(abc,succ(Mid),aLast)
else
MS(abc,succ(Mid),aLast,aTempList);
FirstCount:=succ(Mid-aFirst);
Move(abc[aFirst],aTempList[0],FirstCount*sizeof(pointer));
i:=0;
j:=succ(Mid);
ToInx:=aFirst;
while(i<FirstCount)and(j<=aLast)do
begin
if(aTempList[i]<=abc[j])then
begin
abc[ToInx]:=aTempList[i];
inc(i);
end
else
begin
abc[ToInx]:=abc[j];
inc(j);
end;
inc(ToInx);
end;
if(i<FirstCount)then
Move(aTempList[i],abc[ToInx],(FirstCount-i)*sizeof(pointer));
end;

var
TempList:arrayofInteger;
begin
if(0<High(abc))then
begin
SetLength(TempList,High(abc)div2);
MS(abc,0,High(abc),TempList);
end;
end;

//标准快速排序
procedureQuickSortStd(varabc:arrayofInteger);
procedureQSS(varabc:arrayofInteger;aFirst:Integer;aLast:Integer);
var
L,R:Integer;
Pivot:Integer;
Temp:Integer;
begin
while(aFirst<aLast)do
begin
Pivot:=abc[(aFirst+aLast)div2];
L:=pred(aFirst);
R:=succ(aLast);
whiletruedo
begin
repeat
dec(R);
until(abc[R]<=Pivot);

repeat
inc(L);
until(abc[L]>=Pivot);

if(L>=R)then
Break;

Temp:=abc[L];
abc[L]:=abc[R];
abc[R]:=Temp;
end;
if(aFirst<R)then
QSS(abc,aFirst,R);
aFirst:=succ(R);
end;
end;

begin
QSS(abc,0,High(abc));
end;

//无递归的快速排序
procedureQuickSortNoRecurse(varabc:arrayofInteger);
procedureQSNR(varabc:arrayofInteger;aFirst:Integer;aLast:Integer);
var
L,R:Integer;
Pivot:Integer;
Temp:Integer;
Stack:array[0..63]ofInteger;{allowsfor2billionitems}
SP:Integer;
begin
Stack[0]:=aFirst;
Stack[1]:=aLast;
SP:=2;
while(SP<>0)do
begin
dec(SP,2);
aFirst:=Stack[SP];
aLast:=Stack[SP+1];
while(aFirst<aLast)do
begin
Pivot:=abc[(aFirst+aLast)div2];
L:=pred(aFirst);
R:=succ(aLast);
whiletruedo
begin
repeat
dec(R);
until(abc[R]<=Pivot);
repeat
inc(L);
until(abc[L]>=Pivot);
if(L>=R)then
Break;
Temp:=abc[L];
abc[L]:=abc[R];
abc[R]:=Temp;
end;
if(R-aFirst)<(aLast-R)then
begin
Stack[SP]:=succ(R);
Stack[SP+1]:=aLast;
inc(SP,2);
aLast:=R;
end
else
begin
Stack[SP]:=aFirst;
Stack[SP+1]:=R;
inc(SP,2);
aFirst:=succ(R);
end;
end;
end;
end;

begin
QSNR(abc,0,High(abc));
end;

//随机的快速排序
procedureQuickSortRandom(varabc:arrayofInteger);
procedureQSR(varabc:arrayofInteger;aFirst:Integer;aLast:Integer);
var
L,R:Integer;
Pivot:Integer;
Temp:Integer;
begin
while(aFirst<aLast)do
begin
R:=aFirst+Random(aLast-aFirst+1);
L:=(aFirst+aLast)div2;
Pivot:=abc[R];
abc[R]:=abc[L];
abc[L]:=Pivot;
L:=pred(aFirst);
R:=succ(aLast);
whiletruedo
begin
repeat
dec(R);
until(abc[R]<=Pivot);
repeat
inc(L);
until(abc[L]>=Pivot);
if(L>=R)then
Break;
Temp:=abc[L];
abc[L]:=abc[R];
abc[R]:=Temp;
end;
if(aFirst<R)then
QSR(abc,aFirst,R);
aFirst:=succ(R);
end;
end;

begin
QSR(abc,0,High(abc));
end;

//中间值的快速排序
procedureQuickSortMedian(varabc:arrayofInteger);
procedureQSM(varabc:arrayofInteger;aFirst:Integer;aLast:Integer);
var
L,R:Integer;
Pivot:Integer;
Temp:Integer;
begin
while(aFirst<aLast)do
begin
if(aLast-aFirst)>=2then
begin
R:=(aFirst+aLast)div2;
if(abc[aFirst]>abc[R])then
begin
Temp:=abc[aFirst];
abc[aFirst]:=abc[R];
abc[R]:=Temp;
end;
if(abc[aFirst]>abc[aLast])then
begin
Temp:=abc[aFirst];
abc[aFirst]:=abc[aLast];
abc[aLast]:=Temp;
end;
if(abc[R]>abc[aLast])then
begin
Temp:=abc[R];
abc[R]:=abc[aLast];
abc[aLast]:=Temp;
end;
Pivot:=abc[R];
end
else
Pivot:=abc[aFirst];
L:=pred(aFirst);
R:=succ(aLast);
whiletruedo
begin
repeat
dec(R);
until(abc[R]<=Pivot);
repeat
inc(L);
until(abc[L]>=Pivot);
if(L>=R)then
Break;
Temp:=abc[L];
abc[L]:=abc[R];
abc[R]:=Temp;
end;
if(aFirst<R)then
QSM(abc,aFirst,R);
aFirst:=succ(R);
end;
end;

begin
QSM(abc,0,High(abc));
end;

//优化插入的快速排序
procedureQuickSort(varabc:arrayofInteger);
const
QSCutOff=15;

procedureQSInsertionSort(varabc:arrayofInteger;aFirst:Integer;aLast:Integer);
var
i,j:Integer;
IndexOfMin:Integer;
Temp:Integer;
begin
IndexOfMin:=aFirst;
j:=aFirst+QSCutOff;{!!.01}
if(j>aLast)then
j:=aLast;
fori:=succ(aFirst)tojdo
ifabc[i]<abc[IndexOfMin]then
IndexOfMin:=i;
if(aFirst<>IndexOfMin)then
begin
Temp:=abc[aFirst];
abc[aFirst]:=abc[IndexOfMin];
abc[IndexOfMin]:=Temp;
end;
{nowsortviafastinsertionmethod}
fori:=aFirst+2toaLastdo
begin
Temp:=abc[i];
j:=i;
whileTemp<abc[j-1]do
begin
abc[j]:=abc[j-1];
dec(j);
end;
abc[j]:=Temp;
end;
end;

procedureQS(varabc:arrayofInteger;aFirst:Integer;aLast:Integer);
var
L,R:Integer;
Pivot:Integer;
Temp:Integer;
Stack:array[0..63]ofInteger;{allowsfor2billionitems}
SP:Integer;
begin
Stack[0]:=aFirst;
Stack[1]:=aLast;
SP:=2;

while(SP<>0)do
begin
dec(SP,2);
aFirst:=Stack[SP];
aLast:=Stack[SP+1];

while((aLast-aFirst)>QSCutOff)do
begin
R:=(aFirst+aLast)div2;
if(abc[aFirst]>abc[R])then
begin
Temp:=abc[aFirst];
abc[aFirst]:=abc[R];
abc[R]:=Temp;
end;
if(abc[aFirst]>abc[aLast])then
begin
Temp:=abc[aFirst];
abc[aFirst]:=abc[aLast];
abc[aLast]:=Temp;
end;
if(abc[R]>abc[aLast])then
begin
Temp:=abc[R];
abc[R]:=abc[aLast];
abc[aLast]:=Temp;
end;
Pivot:=abc[R];

L:=aFirst;
R:=aLast;
whiletruedo
begin
repeat
dec(R);
until(abc[R]<=Pivot);
repeat
inc(L);
until(abc[L]>=Pivot);
if(L>=R)then
Break;
Temp:=abc[L];
abc[L]:=abc[R];
abc[R]:=Temp;
end;

if(R-aFirst)<(aLast-R)then
begin
Stack[SP]:=succ(R);
Stack[SP+1]:=aLast;
inc(SP,2);
aLast:=R;
end
else
begin
Stack[SP]:=aFirst;
Stack[SP+1]:=R;
inc(SP,2);
aFirst:=succ(R);
end;
end;
end;
end;

begin
QS(abc,0,High(abc));
QSInsertionSort(abc,0,High(abc));
end;

//堆排序
procedureHeapSort(varabc:arrayofInteger);
procedureHSTrickleDown(varabc:arrayofInteger;root,count:Integer);
var
KKK:Integer;
begin
abc[0]:=abc[root];
KKK:=2*root;
whileKKK<=countdo
begin
if(KKK<count)and(abc[KKK]<abc[KKK+1])then
inc(KKK);
ifabc[0]<abc[KKK]then
begin
abc[root]:=abc[KKK];
root:=KKK;
KKK:=2*root;
end
else
KKK:=count+1;
end;
abc[root]:=abc[0];
end;

var
Inx:Integer;
ItemCount:Integer;
tmp:Integer;
begin
ItemCount:=High(abc)-Low(abc)+1;
forInx:=ItemCountdiv2downto1do
begin
HSTrickleDown(abc,Inx,ItemCount);
end;

forInx:=ItemCountdownto2do
begin
tmp:=abc[1];
abc[1]:=abc[Inx];
abc[Inx]:=tmp;
HSTrickleDown(abc,1,Inx-1);
end;
end;

end.