第二小整数
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 8299 Accepted Submission(s): 5227 Problem Description 求n个整数中倒数第二小的数。每一个整数都独立看成一个数，比如，有三个数分别是1，1，3，那么，第二小的数就是1。 Input 输入包含多组测试数据。
输入的第一行是一个整数C，表示有C测试数据；
每组测试数据的第一行是一个整数n，表示本组测试数据有n个整数（2<=n<=10），接着一行是 n个整数 (每个数均小于100); Output 请为每组测试数据输出第二小的整数，每组输出占一行。 Sample Input 221 231 1 3 Sample Output 21 Author yifenfei Source 绍兴托普信息技术职业技术学院——第二届电脑文化节程序设计竞赛 来源： <http://acm.hdu.edu.cn/showproblem.php?pid=2561> 这是一个求第k大的类似问题，转化一下就是第k小。
不过这个题目数据很小，就是拿来卖萌的，排个序就好了。
1 #include <stdio.h>
2 #include <algorithm>
3 int main()
4 {
5 int C, n, arr[11];
6 scanf("%d", &C);
7 while(C--) {
8 scanf("%d", &n);
9 for(int i=0; i<n; i++)
10 scanf("%d", arr+i);
11 std::sort(arr, arr+n);
12 printf("%d\n", arr[1]);
13 }
14 return 0;
15 }
不过下午上机实在无聊，于是手痒写了快排思想的第k小。
有学过快排的都很容易理解了，partition把数组分成两份，如果k（也就是2）在左边区间就对左边区间求第k小，或者在右边区间求。注意下标从0开始的话，k要减一下。
1 #include <stdio.h>
2 #include <algorithm>
3
4 int partition(int *arr, int p, int q) {
5 int pivot=arr[p];
6 int i=p, j=q;
7 while(i<j) {
8 while(arr[j]>=pivot&&i<j)
9 --j;
10 arr[i]=arr[j];
11 while(arr[i]<=pivot&&i<j)
12 ++i;
13 arr[j]=arr[i];
14 }
15 arr[i]=pivot;
16 return i;
17 }
18
19 int KthMin(int *arr, int p, int q, int k) {
20 int m=partition(arr, p, q);
21 if(m<k-1)
22 return KthMin(arr, m+1, q, k);
23 else if(m>k-1)
24 return KthMin(arr, p, m-1, k);
25 else
26 return arr[m];
27 }
28
29 int main()
30 {
31 int C, n, arr[11];
32 scanf("%d", &C);
33 while(C--) {
34 scanf("%d", &n);
35 for(int i=0; i<n; i++)
36 scanf("%d", arr+i);
37 printf("%d\n", KthMin(arr, 0, n-1, 2));
38 }
39 return 0;
40 }