4.3希尔排序

　　基本思想：将整个无序序列分割成若干小的子序列分别进行插入排序或冒泡排序。

　　序列分割方法：将相隔某个增量h的元素构成一个子序列。在排序过程中，逐次减小这个增量，最后当h减到1时，进行一次插入排序或冒泡排序，排序就完成。增量序列一般采用：d1=n div 2 ,di=di-1 div 2 ；i=2,3,4.....其中n为待排序序列的长度。

　　程序1:(子序列是插入排序)

　　program xepx;

　　const n=7;

　　type

　　arr=array[1..n] of integer;

　　var

　　a:arr;

　　i,j,t,d:integer;

　　bool:boolean;

　　begin

　　write('input data:');

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

　　writeln;

　　d:=n;

　　while d>1 do

　　begin

　　d:=d div 2;

　　for j:=d+1 to n do

　　begin

　　t:=a[j];i:=j-d;

　　while (i>0) and (a[i]>t) do

　　begin a[i+d]:=a[i];i:=i-d;end;

　　a[i+d]:=t;

　　end;

　　end;

　　write('output data:');

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

　　writeln;

　　end.

　　程序2:(子序列是冒泡排序)

　　program xepx;

　　const n=7;

　　type

　　arr=array[1..n] of integer;

　　var

　　a:arr;

　　i,temp,d:integer;

　　bool:boolean;

　　begin

　　write('input data:');

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

　　writeln;

　　d:=n

　　while d>1 do

　　begin

　　d:=d div 2;

　　repeat

　　bool:=true;

　　for i:=1 to n-d do

　　if a[i]>a[i+d] then

　　begin temp:=a[i];a[i]:=a[i+d];a[i+d]:=temp; bool:=false end;

　　until bool;

　　end;

　　write('output data:');

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

　　writeln;

　　end.