1.快排，就是每个元素都归位，如果某一元素刚好在k位那他就是第k大
第一个元素temp 然后第1位为 i  最后一个为j    从j开始j--，如果遇到比temp大的应该在左边，放入i 然后i++，直到比temp小的应该放在右边 j的位置 然后继续j--，  直到  i=j
本题需要使用快速排序的思想，快速排序：每次移动，可以找到一个标杆元素，然后将大于它的移到左边，小于它的移到右边，由此整个数组划分成为两部分，然后分别对左边和右边使用同样的方法进行排序，不断划分左右子段，直到整个数组有序。这也是分治的思想，将数组分化成为子段，分而治之。
  • step 1：进行一次快排，大元素在左，小元素在右，得到的中轴p点。
  • step 2：如果 p - low + 1 = k ，那么p点就是第K大。
  • step 3：如果 p - low + 1 > k，则第k大的元素在左半段，更新high = p - 1，执行step 1。
  • step 4：如果 p - low + 1 < k，则第k大的元素在右半段，更新low = p + 1, 且 k = k - (p - low + 1)，排除掉前面部分更大的元素，再执行step 1.
classSolution {
public:
    //常规的快排划分，但这次是大数在左边
    int partion(vector<int>& a, intlow, inthigh){
        int temp = a[low];
        while(low < high){
            //小于标杆的在右
            while(low < high && a[high] <= temp)  // 交换完a【high 】一定大于temp 不然怎么会交换呢，然后成立必然进入high--，直到找到一个大于temp的放到左边即下面的else a[low] = a[high];
                high--;
            if(low == high)
                break;
            else
                a[low] = a[high];
            //大于标杆的在左
            while(low < high && a[low] >= temp)
                low++;
            if(low == high)
                break;
            else
                a[high] = a[low];
        }
        a[low] = temp;
        returnlow;
    }
    intquickSort(vector<int>& a, intlow, inthigh, intK){
        //先进行一轮划分，p下标左边的都比它大，下标右边都比它小
        intp = partion(a, low, high);


//这是如何继续划分
        //若p刚好是第K个点，则找到
        if(K == p - low + 1) 
            returna[p];
        //从头到p超过k个数组，则目标在左边
        elseif(p - low + 1> K)  
            //递归左边
            returnquickSort(a, low, p - 1, K); 
        else 
            //否则，在右边,递归右边,但是需要减去左边更大的数字的数量
            returnquickSort(a, p + 1, high, K - (p - low + 1)); 
    }
    intfindKth(vector<int> a, intn, intK) {
        returnquickSort(a, 0, n - 1, K);
    }
};