(找第k大的数)给定一个长度为1000000的无序正整数序列,以及另一个数n(1<=n<=1000000),接下来以类似快速排序的方法找到序列中第n大的数(关于第n大的数:例如序列{1,2,3,4,5,6}中第3大的数是4)
Var a:array[1..1000000] of integer;
n,m,ans:integer;
procedure swap(var a,b:integer);
var t:integer;
begin
if (a<>b) then begin
t:=a; a:=b; b:=t;
end;
end;
Function FindKth(left,right,n:integer):integer;
Var tmp,value,i,j:integer;
begin
if left=right then exit(left);
tmp:=random(right-left)+left;
swap(a[tmp],a[left]);
value:= a[left] ;
i:=left; j:=right;
while i<j do
begin
while (i<j) and ( a[j]<value ) do dec(j);
if i<j then begin
a:=a[j];inc(i);
end else break;
while (i<j) and ( a[i]>value ) do inc(i);
if i<j then begin
a[j]:=a[i]; dec(j);
end else break;
end;
a[i]:=value ;
if i<n then begin inc(i); exit(FindKth( i,right,n ));end;
if i>n then begin dec(j); exit( FindKth(left,i,n) );end;
exit(i);
end;
var i:integer;
begin
randomize;
ans:=-1;
m:=5;
for i:=1 to m do
read(a[i]);
read(n);
ans:=FindKth(1,m,n);
writeln(a[ans]);
end.