寻找第k大

思路：快排+二分

1.对于快排，先设置第一个数为基准数

2.设置一个指针i指向区间的左端点，设置一个指针j指向区间的右端点

3.只要两个指针没有相遇，即i<j,就继续循环

4.i指针只要还没有与j指针相遇（i<j）,如果要进行升序，就让i去找比基准大的数，这样交换后就是大数在后

5.j指针只要还没有与j指针相遇（i<j）,如果要进行升序，就让j去找比基准小的数，这样交换后就是小数在前

5.降序操作相反

6.只要两个指针没有相遇，就将两个数交换

7.最后将基准数与指针相遇的位置的值进行交换

8.递归求[l,i-1]区间和[i+1,r]区间进行快排

用二分的思想去找第k大的数，因为已经是有序的，所以可以用二分进行查找

代码：

class Solution {
public:
    //快排函数
    int quick_sort(vector<int>& a,int l,int r,int k){
        //设置一个基准数：一般设置第一个数为基准数
        //设置两个指针：左指针指向区间的左端点，右指针指向区间的右端点
        int temp=a[l];
        int i=l,j=r;
        //只要两个指针还没有相遇，就继续循环
        while(i<j){
            //只要指针没有相遇，且由于要降序，所以j指针是去找比基准数大的，之后交换后就可以使得大的数在前面
            while(i<j&&a[j]<=temp){
                j--;
            }
            //只要两个指针还没有相遇，且是降序，所以i指针是去找比基准数小的数，之后交换后就可以使小的数在后面
            while(i<j&&a[i]>=temp){
                i++;
            }
            //只要指针没有相遇，就交换两者的值
            if(i<j){
               swap(a[i],a[j]);
            }
        }
        //最后将基准数与相遇的那个位置的值交换，注意交换的a数组中的元素，所以是a[l]而不是temp
        swap(a[i],a[l]);
        //如果发现刚好找到第k个数，就返回第k大的数的值
        if(i+1==k){
            return a[i];
        }else if(i+1<k){
            //否则就去[i+1,r]的区间继续找
            return quick_sort(a,i+1,r,k);
        }else {
            //否则就去[l,i-1]的区间找第k大的数
            return quick_sort(a,l,i-1,k);
        }
    }
    int findKth(vector<int>& a, int n, int K) {
        //快排，传入需要排序的序列的区间的左右端点，由于下标从0开始，所有区间的所有端点是0和n-1
        return quick_sort(a,0,n-1,K);
    }
};