1.题目分析：
查找无序数组中的第K大数，直观感觉便是先排好序再找到下标为K-1的元素，时间复杂度O(NlgN)。在此，我们想探索是否存在时间复杂度 < O(NlgN)，而且近似等于O(N)的高效算法。
还记得我们快速排序的思想麽？通过“partition”递归划分前后部分。在本问题求解策略中，基于快排的划分函数可以利用“夹击法”，不断从原来的区间[0,n-1]向中间搜索第k大的数，大概搜索方向见下图：
2.参考代码：
1 #include <cstdio>
2
3 #define swap(x,y){int temp=x;x=y;y=temp;}
4
5 using namespace std;
6
7
8
9 const int maxn=1e5;
10
11 int a[maxn];
12
13
14
15 int part(int *arr,int p,int q){
16
17 int i=p-1;
18
19 for(int j=p;j<q;j++) if(arr[j]<a[q]){
20
21 i++;
22
23 swap(arr[i],arr[j]);
24
25 }
26
27 i=i+1;
28
29 swap(arr[i],arr[q]);
30
31 return i;
32
33 }
34
35 int findK(int *arr,int n,int k){
36
37 int p=0,q=n-1;
38
39 while(p<q){
40
41 //int m=p+(q-p)/2;
42
43 int f=part(arr,p,q);
44
45 //printf("f=%d\n",f); //for tested
46
47 if(f==k){
48
49 return arr[k];
50
51 }else if(f>k){
52
53 q=f-1;
54
55 }else{
56
57 p=f+1;
58
59 }
60
61 }
62
63 return arr[k]; //needed
64
65 }
66
67 int main(){
68
69 int n,k;
70
71 /*
72
73 *input includes 2 integers. n indicates the num of elements ,
74
75 *k means for the kth larger num to be found
76
77 */
78
79 while(scanf("%d%d",&n,&k)==2){
80
81 for(int i=0;i<n;i++) scanf("%d",&a[i]);
82
83 int ans=findK(a,n,k-1);
84
85 printf("%d\n",ans);
86
87 }
88
89 return 0;
90
91 }
92
93 /*
94
95 data for the test:
96
97 4 2
98
99 1 5433 11 2
100
101 4 3
102
103 1 5433 11 2
104
105 4 4
106
107 1 5433 11 2
108
109 */
110
111
3.测试结果：
结语：
本算法实现仅适用常规情况，如果K=1或2聪明的你应该要知道不必套用本文的算法，简单遍历保存最大即可，所以说具体问题还得具体分析^_^