查找第k小元素

查找第k小元素

查找第k小元素即在n个元素中（未排序）找到第k小的元素。方法同快速排序，采用递归方式。

程序如下：

program kspv;
const n=7;
type
arr=array[1..n] of integer;
var
b:arr;
i,k:integer;
function p(s,t:integer):integer;
var i,j,t1,x:integer;
begin
  i:=s;j:=t;x:=b;
  repeat
   while (b[j]>=x) and (j>i) do j:=j-1;
    if j>i then begin t1:=b; b:=b[j];b[j]:=t1;end;
   while (b<=x) and (i<j) do i:=i+1;
    if i<j then begin t1:=b[j];b[j]:=b;b:=t1; end
  until i=j;
  b:=x;
  p:=i;
end;
function find(s,t,k:integer):integer;
var p1,q:integer;
begin
if s=t then find:=b else
  begin
   p1:=p(s,t);
   q:=p1-s+1;
   if k<=q then find:=find(s,p1,k) else find:=find(p1+1,t,k-q);
end;
end;
begin
write('input data:');
for i:=1 to n do read(b);readln;
write('input k:');read(k);
write('output data:');
writeln('kthsmall:=',find(1,n,k));
end.