归并排序

归并排序

归并就是将多个有序的数列合成一个有序的数列。将两个有序序列合并为一个有序序列叫二路归并(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;

typearrl1=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('Enterl1(sorted):');

for i:=1 to mdo read(a);

write('Enterl2(sorted):');

for i:=1 to ndo read(b);

i:=1;j:=1;k:=0;

while (i<=m)and (j<=n) do

begin

k:=k+1;

ifa<=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 thenfor r:=i to m do c[m+r]:=a[r];

if j<=nthen  for r:=j to n do c[n+r]:=b[r];

writeln('Outputdata:');

for i:=1 to m+ndo 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:=r 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.

返回