“第/前k大数问题”指的是在长度为n(n>=k)的乱序数组S中找出从大到小顺序的第k个数的问题（当然类似地也有“第K小数问题”）。下面是几种常见解决方法。
解法1： 我们可以对这个乱序数组按照从大到小先行排序，排序方法可以根据实际情况选择，最优情况是O(n*logn)，然后取出前k大，总的时间复杂度应为O(n*logn + k)。
解法2： 利用选择排序或交互排序，K次选择后就可以得到第k大的数。总的时间复杂度为O(n*k) 。
解法3： 利用快速排序的思想，从数组S中随机找出一个元素X，把数组分为两部分Sa和Sb。Sa中的元素大于等于X，Sb中元素小于X。这时有两种情况：
1. Sa中元素的个数小于k，则Sb中的第k-|Sa|个元素即为第k大数；
2. Sa中元素的个数大于等于k，则返回Sa中的第k大数。时间复杂度近似为O(n)。
解法4： 二分[Smin,Smax]查找结果X，统计X在数组中出现，且整个数组中比X大的数目为k-1的数即为第k大数。时间复杂度平均情况为O(n*logn) 。
解法5：用O(4*n)的方法对原数组建最大堆，然后pop出k次即可。时间复杂度为O(4*n + k*logn) 。
解法6：维护一个大小为K的最大堆，对于数组中的每一个元素判断与堆顶的大小，若堆顶较小，则不管，否则，弹出堆顶，将当前值插入到堆中。时间复杂度O(n*logk) 。
解法7：利用hash保存数组中元素Si出现的次数，利用计数排序的思想，线性从小到大扫描过程中，前面有k-1个数则为第k大数，平均情况下时间复杂度O(n) 。
附注：
STL中可以用nth_element求得第n大的数，使用的是解法3中的思想，
template<class RandomAccessIterator> inline
void nth_element(RandomAccessIterator first,
RandomAccessIterator nth,
RandomAccessIterator last)
它的一个示例程序如下：
01 // Functions:
02 // nth_element : Partition the elements in a sequence by its nth element.
03
04 #pragma warning(disable: 4786)
05
06 #include <iostream>
07 #include <algorithm>
08 #include <functional>
09 #include <vector><BR/>
10 using namespace std;
11
12 void main()
13 {
14 const int VECTOR_SIZE = 8 ;
15
16 // Define a template class vector of int
17 typedef vector<int,allocator<int> > IntVector ;
18
19 //Define an iterator for template class vector of strings
20 typedef IntVector::iterator IntVectorIt ;
21
22 IntVector Numbers(VECTOR_SIZE) ;
23
24 IntVectorIt start,end,it ;
25
26 // Initialize vector Numbers
27 Numbers[0] = 4 ;
28 Numbers[1] = 10;
29 Numbers[2] = 70 ;
30 Numbers[3] = 30 ;
31 Numbers[4] = 10;
32 Numbers[5] = 69 ;
33 Numbers[6] = 96 ;
34 Numbers[7] = 100;
35
36 start = Numbers.begin() ; // location of first
37 // element of Numbers
38
39 end = Numbers.end() ; // one past the location
40 // last element of Numbers
41
42 cout << "Before calling nth_elementn" << endl ;
43
44 // print content of Numbers
45 cout << "Numbers { " ;
46 for(it = start; it != end; it++)
47 cout << *it << " " ;
48 cout << " }n" << endl ;
49
50 // partition the elements by the 4th element
51 nth_element(start,start+4,end) ;
52
53 cout << "After calling nth_elementn" << endl ;
54
55 cout << "Numbers { " ;
56 for(it = start; it != end; it++)
57 cout << *it << " " ;
58 cout << " }n" << endl ;
59 }
60
61 Program Output is:
62
63 Before calling nth_element
64
65 Numbers { 4 10 70 30 10 69 96 100 }
66
67 After calling nth_element
68
69 Numbers { 4 10 10 30 69 70 96 100 }
参考：
http://www.cnblogs.com/drizzlecrj/archive/2009/08/23/1537910.html
http://support.microsoft.com/kb/158000/zh-cn
http://www.19880711.com/blog/read.php?1653
