Pascal 军事机密

军事机密（secret.pas）
【问题描述】
我军方截获的信息由n(n<=30000) 个数字组成，因为是敌国的高端机密，所以一时不能破获最原始的想法就是对这n个数进行从小到大排序，每个数都对应一个序号，然后对第i个是什么数最感兴趣，现在要求编程完成。
【输入格式】
第一行是n，第二行是n个截获的数字，第三行是数字k，接着是k行要输出数的序号。
【输出格式】
k行序号所对对应的数字。
【输入样例】secret.in
5
121 1 126 123 7
3
2
4
3
【输出样例】secret.out
7
123
121

军事机密？只有快排能做，其它超时。
代码：
type
arr=array[1..200000] of longint;
procedure qs(var x:arr;l,r:longint);//快排
var
i,j,m,t:longint;
begin
i:=l;j:=r;m:=x[random(r-l+1)+l] ;
repeat
while x[i]<m do i:=i+1;
while x[j]>m do j:=j-1;
if i<=j then
begin
t:=x[i];x[i]:=x[j];x[j]:=t;
i:=i+1;j:=j-1;
end;
until i>j;
if j>l then qs(x,l,j);
if i<r then qs(x,i,r);
end;
var
a,b:arr;
n,i,t,m:longint;
begin
randomize;
readln(n);
for i:=1 to n do read(a[i]);
qs(a,1,n);
readln(m);
for i:=1 to m do readln(b[i]);
for i:=1 to m do writeln(a[b[i]]);
end.
end.本回答被网友采纳

检查k行序号进行插入排序。

2
4
3
可以得到 234

根据最大最小值检查分布情况
如果分布在集中在 中间，或两端，用快速选择（由快排派生的选择问题的快速算法 ）
如果分布比较分散，快速排序