尋找第k大的數字，有很多方法，最基本的就是將數組按照從大到小的順序排列，找出第k個元素即可。但是這種方法的時間復雜度為o(nlog(n)),我們還能找到更好地方法。下面我們將介紹另外兩種辦法，一種是基于快排Partition的方法，一種是基于partial_sort的方法。
基于快排partition的查找法
利用快速排序的思想，從數組S中隨機找出一個元素X，把數組分為兩部分Sa和Sb。Sa中的元素大于等于X，Sb中元素小于X。這時有兩種情況：
- Sa中元素的個數小于k，則Sb中的第k-|Sa|個元素即為第k大數；
- Sa中元素的個數大于等于k，則返回Sa中的第k大數。時間復雜度近似為O(n)
遞歸法
#include <iostream>using namespace std;//快速排序的劃分函數
int partition(int data[],int i,int j)
//將>=x的元素換到左邊區域
//將<=x的元素換到右邊區域
{if(data==NULL||i<0)throw std::exception("invalued parameter");int index = i+rand()%(j-i+1);//生產隨機數int pivot=data[index];swap(data[i],data[index]);while(i<j){while(i<j&&pivot>=data[j]){j--;}if (i<j){data[i++]=data[j];}while(i<j&&pivot<=data[i]){i++;}if (i<j){data[j--]=data[i];}}data[i]=pivot;return i;
}//線性尋找第k大的數,遞歸法
int random_select(int a[],int l,int r,int k)
{if(k>(r-l+1)||k<1)//k應該在[1,r-l+1]之間throw std::exception("invalued k");int i,j;if (l == r) //遞歸結束{return a[l];}i = partition(a,l,r);//劃分j = i-l+1;//距開始的長度，i為第j大的數字if(k == j) //遞歸結束，找到第K大的數return a[i];if(k < j){return random_select(a,l,i-1,k);//遞歸調用，在前面部分查找第K大的數}elsereturn random_select(a,i+1,r,k-j);//遞歸調用，在后面部分查找第K大的數
}int main()
{int a[]={1,2,3,4,6,6,7,8,10,10};cout<<random_select(a,0,9,1)<<endl;cout<<random_select(a,0,9,5)<<endl;return 0;
}循環法
#include <iostream>using namespace std;//快速排序的劃分函數
int partition(int data[],int len, int i, int j)
//將>=x的元素換到左邊區域
//將<=x的元素換到右邊區域
{if (data == NULL ||len<=0|| i < 0||j>=len)throw std::exception("invalued parameter");int index = i + rand() % (j - i + 1);//生產隨機數int pivot = data[index];swap(data[i], data[index]);while (i < j){while (i < j&&pivot >= data[j]){j--;}if (i < j){data[i++] = data[j];}while (i < j&&pivot <= data[i]){i++;}if (i<j){data[j--] = data[i];}}data[i] = pivot;return i;
}//線性尋找第k大的數，循環法
int random_select(int a[],int len, int k)
{if (a == NULL || len <= 0 || k > len || k <= 0){throw std::exception("invalued parameter");}int i = 0;int j = len - 1;int index = partition(a, len, i, j);while (index+1!= k){if (index+1> k){index = partition(a, len, i, index - 1);}else{index = partition(a, len, index + 1, j);}}int result = a[k-1];return result;}int main()
{int a[] = { 1, 2, 3, 4, 6, 6, 7, 8, 10, 10 };cout << random_select(a,10, 1) << endl;cout << random_select(a, 10,3) << endl;return 0;
}上面兩種辦法均是基于partiton的方法，實際上在C++ STL中也有一個實現查找第k大元素的方法：nth_element.
nth_element
nth_element用于排序一個區間，它使得位置n上的元素正好誰全排序情況下的第n個元素，而且，當nth_element返回的時候，所有按照全排序規則排在位置n之前的元素也都排在位置n之前，按照全排序規則排在n之后的元素全都排在位置n之后。
所以，我們使用nth_element既可以尋找最好的前k個元素，也可以尋找第k大元素。
先看示例：
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
int main()
{int a[10] = { 8, 9, 1, 2, 4, 3, 5, 6, 7, 10 };nth_element(a, a + 5, a + 10, std::greater<int>());cout << "數組中的中間元素是" << a[5] << endl;nth_element(a, a, a + 10, std::greater<int>());cout << "數組中第1大元素為" << a[0] << endl;nth_element(a, a + 1, a + 10, std::greater<int>());cout << "數組中第2大元素是" << a[1] << endl;
}結果為：
數組中的中間元素是5
數組中第1大元素為10
數組中第2大元素是9
請按任意鍵繼續. . .使用說明：
default (1)
template <class RandomAccessIterator>void nth_element (RandomAccessIterator first, RandomAccessIterator nth,RandomAccessIterator last);
custom (2)
template <class RandomAccessIterator, class Compare>void nth_element (RandomAccessIterator first, RandomAccessIterator nth,RandomAccessIterator last, Compare comp);default (1) 使用‘<’作為比較符
custom (2) 可以指定比較運算
nth：實際指的是nth+1大（小）元素，也就是如果你要找前20個最大的，nth=19.
基于partial_sort的查找法
用O(4*n)的方法對原數組建最大堆，然后pop出k次即可。時間復雜度為O(4*n + k*logn)
在C++ STL中同樣有一個部分排序的函數就是partial_sort。
用法：
default (1)
template <class RandomAccessIterator>void partial_sort (RandomAccessIterator first, RandomAccessIterator middle,RandomAccessIterator last);
custom (2)
template <class RandomAccessIterator, class Compare>void partial_sort (RandomAccessIterator first, RandomAccessIterator middle,RandomAccessIterator last, Compare comp);default (1) ：使用‘<’作為比較符
custom (2) ：可以指定比較運算
middle：將前middle個元素排序，比如說我們要找到前10個最小的元素，而且從小到大排列，這時可以使用partial_sort，middle=10.
注意：
partial_sort與上面的nth_element相比，需要對前面最好的n個元素排序，而nth_element只需要找到前面最好的n個元素就可以，不需要知道順序。
而且關于第二個參數的使用上截然不同：partial_sort使用第1個和第2個迭代器指明一段需要排序的區間，根據STL關于區間的定義，第2個參數應該是目標區間外的第一個元素（比如widgets.begin()+20實際指的是第21個元素），而nth_element則使用第2個參數標識出容器中的某個特定位置（比如widgets.begin()+19實際指的是第20個元素）
詳細情況請參考：《理解你的排序操作[(stable_sort,sort,partial_sort,nth_element,stable_partition,partition)》
因此我們可以先部分排序，再直接取第k個元素即可。
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
int main()
{int a[10] = { 8, 9, 1, 2, 4, 3, 5, 6, 7, 10 };partial_sort(a, a + 6, a + 10, std::greater<int>());cout << "數組中的中間元素是" << a[5] << endl;partial_sort(a, a + 2, a + 10, std::greater<int>());cout << "數組中第1大元素為" << a[0] << endl;partial_sort(a, a + 3, a + 10, std::greater<int>());cout << "數組中第2大元素是" << a[1] << endl;
}
