1.问题描述
设计算法实现在一个具有在n各互不相同元素的数组A[1…n]中找出所有前k个最小元素的问题，这里k不是常量，即它是输入数据的一部分。要求算法的时间复杂性为Θ(n)。
2. 具体要求
输入的第一行是一个正整数m，表示测试例个数。接下来几行是m个测试例的数据，每个测试例的数据由三行组成，其中其中，第一行输入一个正整数n，表示元素的个数；第二行输入n个整数，整数之间用一个空格隔开。第三行输入一个正整数k，表示求该组测试例中的前k个最小元素。（设给出的每个整数序列中的元素是唯一的。）
输出：对于每个测试例输出一行，由k个整数组成，表示输入的n个整数中前k个最小元素。整数之间用一个空格隔开。两个测试例的输出数据之间用一个空行隔开。
说明：限于Acm平台，要求输出数据按从小到大排序。算法的时间复杂性也相应地放宽要求。
3. 测试数据
输入：
2
19
56 34 22 7 16 95 46 37 81 12 73 26 19 31 68 42 3 72 51
8
26
8 33 28 17 51 57 49 35 11 25 37 14 3 2 13 52 12 6 2 32 54 5 16 22 23 7
13
输出：
3 7 12 16 19 22 26 31
2 3 5 6 7 8 11 12 13 14 16 17 22
4、程序实现（java）
1
import java.io.*;
2public class Ex3_2
3
{
4
public static void main(String[] args) throws Exception
5
{
6 Ex3_2 yeyunce=new Ex3_2();
7 BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
8 System.out.println("请输入测试例个数:");
9 String str=br.readLine();
10 int m=Integer.parseInt(str);
11 yeyunce.Test(m);
12
13
}
14 public void Test(int m)
15 {
16 int[][] is=new int[m][100];
17 int[] r=new int[m];
18 for(int i=0;i<m;i++)
19 {
20 try
21 {
22 BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
23 System.out.println("总测试例个数为"+m+",现请输入第"+(i+1)+"个用例数组的元素个数，在下一行列出,再接着一行输出要求的最小元素个数:");
24 String str=br.readLine();
25 int d=Integer.parseInt(str);
26 String str2=br.readLine();
27 String[] str3=str2.split(" ");
28 int[] ii=new int[d];
29 for(int j=0;j<d;j++)
30 {
31 ii[j]=Integer.parseInt(str3[j]);
32 }
33 String str4=br.readLine();
34 int k=Integer.parseInt(str4);
35 r[i]=k;
36 if((k>0)&&(k<=d))
37 {
38 qs(ii,0,d-1,k);
39 for(int t=0;t<k;t++)
40 {
41 is[i][t]=ii[t];
42 }
43 }
44 else if(k>d)
45 {
46 System.out.println("前k小元素个数不能大于数组长度！");
47 }
48 System.out.println();
49 }
50 catch(IOException e)
51 {
52 System.out.println(e);
53 }
54 }
55 System.out.println("结果为：");
56 for(int p=0;p<m;p++)
57 {
58 System.out.println();
59 for(int q=0;q<r[p];q++)
60 {
61 System.out.print(is[p][q]+" ");
62 }
63 System.out.println();
64 }
65 System.out.println();
66 }
67 public static void qs(int[] data,int left,int right,int k)
68 {
69 int i=0;
70 int j=0;
71 if(left<right)
72 {
73 i=left+1;
74 while(data[i]<data[left])
75 {
76 if(i+1>right)
77 {
78 break;
79 }
80 i++;
81 }
82 j=right;
83 while(data[j]>data[left])
84 {
85 j--;
86 }
87 while(i<j)
88 {
89 int temp=data[i];
90 data[i]=data[j];
91 data[j]=temp;
92 i++;
93 while(data[i]<data[left])
94 {
95 i++;
96 }
97 j--;
98 while(data[j]>data[left])
99 {
100 j--;
101 }
102 }
103 int temp=data[left];
104 data[left]=data[j];
105 data[j]=temp;
106 if(j-left+1>k)
107 {
108 qs(data,left,j-1,k);
109 }
110 else if(j-left+1<k)
111 {
112 qs(data,j+1,right,k-j-1);
113 }
114 }
115 }
116
}
5、运行结果
