宜昌一中 2009NOIP 复习资料
until i>j;
if i<w then qsort(data,i,w);
if t<j then qsort(data,t,j);
end;
·冒泡排序
procedure bsort(var data:arr);
var i,j:integer;
begin
for i:=1 to n-1 do
for j:=n downto i+1 do
if a[j-1]>a[j] then
begin
a[0]:=a[j];
a[j]:=a[j-1];
a[j-1]:=a[0];
end;
end;
·堆排序(by TT 大牛)
procedure swap(i,j:longint);//
交换
var t:longint;
begin
t:=a[i];
a[i]:=a[j];
a[j]:=t;
end;
procedure heapdown(i:longint);
var l,r:longint;
m:longint;
begin
l:=i shl 1;{l:=i*2;l
是
i
的左儿子
}
r:=i shl 1+1;{r:=(i*2)+1;r
是
i
的右儿
子
}
if (l<=n) and (a[l]>a[i]) then m:=l
else m:=i;
if (r<=n) and (a[r]>a[m]) then
m:=r;
if i<>m then
begin
swap(i,m);
heapdown(m);
end;
end;
procedure heapup(i:longint);
var f:longint;
begin
f:=i shr 1;{f:=i div 2;f
是
i
的父亲
}
if a[f]<a[i] then
begin
swap(i,f);
heapup(f);
end;
end;
procedure buildheap;//
建堆(大根堆)
var i:longint;
begin
for i:=n shr 1 downto 1 do
heapdown(i);
end;
·堆排序(by yym 大牛)
procedure swap(i,j:longint);
var t:longint;
begin
t:=a[i];
a[i]:=a[j];
a[j]:=t;
end;
procedure build(i,m:longint); //
建 堆
(小根堆)
begin
while i*2<=m do
begin
i:=i*2;
if (i<m) and (a[i+1]>a[i]) then
inc(i);
if (a[i]>a[i div 2]) then
swap(i div 2,i)
else break;
end;
end;
procedure deal; //
主程序
begin
for i:=n div 2 downto 1 do
build(i,n);
for i:=n downto 2 do
4