堆排序 堆:设有数据元素的集合(R1,R2,R3,...Rn)它们是一棵顺序二叉树的结点且有 Ri<=R2i 和Ri<=R2i+1(或>=) 堆的性质:堆的根结点上的元素是堆中的最小元素,且堆的每一条路径上的元素都是有序的。 堆排序的思想是: 1)建初始堆(将结点[n/2],[ n/2]-1,...3,2,1分别调成堆) 2)当未排序完时 输出堆顶元素,删除堆顶元素,将剩余的元素重新建堆。 程序如下: program duipx;
const n=8;
type arr=array[1..n] of integer;
var a:arr;i:integer;
procedure sift(var a:arr;l,m:integer);
var i,j, t:integer;
begin
i:=l;j:=2*i;t:=a;
while j<=m do
begin
if (j<m) and (a[j]>a[j+1]) then j:=j+1;
if t>a[j] then
begin a:=a[j];i:=j;j:=2*i; end
elseexit;
end;
a:=t;
end;
begin
for i:=1 to n do read(a);
for i:=(n div 2) downto 1 do
sift(a,i,n);
for i:=n downto 2 do
begin
write(a[1]:4);
a[1]:=a;
sift(a,1,i-1);
end;
writeln(a[1]:4);
end.
|