有一个整数数组，请你根据快速排序的思路，找出数组中第K大的数。
给定一个整数数组a,同时给定它的大小n和要找的K(K在1到n之间)，请返回第K大的数，保证答案存在。
测试样例：
[1,3,5,2,2],5,3 返回：21.若不按快排思路，用最大堆实现，建堆复杂度O(n)，插入复杂度O(logn)，总共复杂度O(nlogn)
class Finder { public: int findKth(vector<int> a, int n, int K) { // write code here priority_queue<int> q; for(int i = 0; i < n; ++i){ q.push(a[i]); } for(int i = 0; i < K - 1; ++i){ q.pop(); } return q.top(); } };2.快排思想，先找主元，每次把，排完主元位置，判断主元位置与n-K大小(升序排序)，若主元位置与n-K相等则直接返回该位置，若位置小于n-K，则排序主元右侧，位置大于n-K则排序主元左侧。
时间复杂度：第一次分区，查找了 n 个元素，第二次查找了 n/2 个元素，依次类推，最后区间缩小到 1，复杂度为 n+n/2 + n/4 + ....+1 为O(n)
class Finder { public: int findKth(vector<int> a, int n, int K) { // write code here int res; res = quick_sort(a , 0, n-1, K); return a[res]; } int findPivot(vector<int> &a, int left, int right){ int center = left + (right - left) / 2; if(a[left] > a[center]) swap(a[left], a[center]); if(a[left] > a[right]) swap(a[left], a[right]); if(a[center] > a[right]) swap(a[center], a[right]); swap(a[center], a[right-1]); return a[right-1]; } int quick_sort(vector<int> &a, int left, int right, int K){ if(left < right - 1){ int pivot = findPivot(a, left, right); int i = left, j = right - 1; for(;;){ while(a[++i] < pivot); while(a[--j] > pivot); if(i < j) swap(a[i], a[j]); else break; } swap(a[i], a[right - 1]); if(i == a.size()- K) return i; else if(i > a.size()- K) return quick_sort(a, left, i - 1, K); else return quick_sort(a, i + 1, right, K); } else if(left == right - 1){ if(a[left] > a[right]) swap(a[left], a[right]); if(left == a.size()- K) return left; else return right; } } };
