归并排序
归并就是将多个有序的数列合成一个有序的数列。将两个有序序列合并为一个有序序列叫二路归并(merge).归并排序就是n长度为1的子序列,两两归并最后变为有序的序列。
1.二路归并
例1:将有序表L1=(1,5,7),L2=(2，3,4,6,8，9,10)合并一个有序表 L.
program gb;
const m=3;n=7;
type arrl1=array[1..m] of integer;
arrl2=array[1..n] of integer;
arrl=array[1..m+n] of integer;
var a:arrl1;
b:arrl2;
c:arrl;
i,j,k,r:integer;
begin
write('Enter l1(sorted):');
for i:=1 to m do read(a);
write('Enter l2(sorted):');
for i:=1 to n do read(b);
i:=1;j:=1;k:=0;
while (i<=m) and (j<=n) do
begin
k:=k+1;
if a<=b[j] then begin c[k]:=a;i:=i+1; end
else begin c[k]:=b[j];j:=j+1;end;
end;
if i<=m then for r:=i to m do c[m+r]:=a[r];
if j<=n then for r:=j to n do c[n+r]:=b[r];
writeln('Output data:');
for i:=1 to m+n do write(c:5);
writeln;
end.
2.归并排序
program gbpx;
const maxn=7;
type arr=array[1..maxn] of integer;
var a,b,c:arr;
i:integer;
procedure merge(r:arr;l,m,n:integer;var r2:arr);
var i,j,k,p:integer;
begin
i:=l;j:=m+1;k:=l-1;
while (i<=m)and (j<=n) do
begin
k:=k+1;
if r<=r[j] then begin r2[k]:=r;i:=i+1 end
else begin r2[k]:=r[j];j:=j+1 end
end;
if i<=m then
for p:=i to m do begin k:=k+1;r2[k]:=r[p] end;
if j<=n then
for p:=j to n do begin k:=k+1;r2[k]:=r[p] end;
end;
procedure mergesort( var r,r1:arr;s,t:integer);
var k:integer; c:arr;
begin
if s=t then r1[s]:=r[s] else
begin
k:=(s+t) div 2;
mergesort(r,c,s,k);
mergesort(r,c,k+1,t);
merge(c,s,k,t,r1)
end;
end;
begin
write('Enter data:');
for i:= 1 to maxn do
read(a);
mergesort(a,b,1,maxn);
for i:=1 to maxn do
write(b:9);
writeln;
end.
