4.5 归并排序

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

　　write('Enter l2(sorted):');

　　for i:=1 to n do read(b[i]);

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

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

　　begin

　　k:=k+1;

　　if a[i]<=b[j] then begin c[k]:=a[i];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[i]: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[i]<=r[j] then begin r2[k]:=r[i];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[i]);

　　mergesort(a,b,1,maxn);

　　for i:=1 to maxn do

　　write(b[i]:9);

　　writeln;

　　end.

　　4.6 线形排序

　　以上我们讨论的算法均是基于比较的排序算法，在排序算法中有基于数字本身的算法：计数、桶、基数排序。

　　1.计数排序

　　基本思想是对于序列中的每一元素x,确定序列中小于x的元素的个数。

　　例：n个整数序列且每个值在[1,m],排序之。

　　program jspx;

　　const m=6;n=8;

　　var i,j:integer;

　　a,b:array[1..n] of integer;

　　c:array[1..m] of integer;

　　begin

　　writeln('Enter data:');

　　for i:=1 to n do read(a[i]);

　　for i:=1 to m do c[i]:=0;

　　for i:=1 to n do c[a[i]]:=c[a[i]]+1;

　　for i:=2 to m do c[i]:=c[i]+c[i-1];

　　for i:=n downto 1 do

　　begin

　　b[c[a[i]]]:=a[i];

　　c[a[i]]:=c[a[i]]-1;

　　end;

　　writeln('Sorted data:');

　　for i:= 1 to n do

　　write(b[i]:6);

　　end.

　　2.桶排序

　　桶排序的思想是若待排序的记录的关键字在一个明显有限范围内(整型)时,可设计有限个有序桶,每个桶装入一个值,顺序输出各桶的值,将得到有序的序列。

　　例：输入n个0到100之间的整数，由小到大排序输出。

　　program tpx;

　　const n=7;

　　var b:array[0..100] of integer;

　　k:0..100;

　　i:integer;

　　begin

　　write('Enter date:(0-100)');

　　for i:=0 to 100 do b[i]:=0;

　　for i:= 1 to n do

　　begin

　　read(k);

　　b[k]:=b[k]+1;

　　end;

　　writeln('Output data:');

　　for i:=0 to 100 do

　　while b[i]>0 do begin write(i:6);b[i]:=b[i]-1 end;

　　writeln;

　　end.

　　3.基数排序

　　基本思想是对n个元素依次按k,k-1,...1位上的数字进行桶排序。

　　program jspx;

　　const n=8;

　　type link=^node;

　　node=record

　　data:integer;

　　next:link;

　　end;

　　var i,j,l,m,k:integer;

　　a:array[1..n] of integer;

　　s:string;

　　q,head:array[0..9] of link;

　　p,p1:link;

　　begin

　　writeln('Enter data:');

　　for i:=1 to n do read(a[i]);

　　for i:=5 downto 1 do

　　begin

　　for j:=0 to 9 do

　　begin

　　new(head[j]);

　　head[j]^.next:=nil;

　　q[j]:=head[j]

　　end;

　　for j:=1 to n do

　　begin

　　str(a[j],s);

　　for k:=1 to 5-length(s) do

　　s:='0'+ s;

　　m:=ord(s[i])-48;

　　new(p);

　　p^.data:=a[j];

　　p^.next:=nil;

　　q[m]^.next:=p;

　　q[m]:=p;

　　end;

　　l:=0;

　　for j:=0 to 9 do

　　begin

　　p:=head[j];

　　while p^.next<>nil do

　　begin

　　l:=l+1;p1:=p;p:=p^.next;dispose(p1);a[l]:=p^.data;

　　end;

　　end;

　　end;

　　writeln('Sorted data:');

　　for i:= 1 to n do

　　write(a[i]:6);

　　end.