题解 | #寻找第K大#

快速排序（从大到小排序）每一趟都能保证基准左边的数都比基准大，基准右边的数都比基准小。设基准的位置为i，则基准为第i+1大，若k等于i+1则符合条件退出。若i+1>k则说明第k大的数在基准左边，否则在右边。

class Solution {
public:
    int findKth(vector<int> a, int n, int K) {
        // write code here

        //将数组首元素作为每一轮比较的基准，比基准大的数放在左边，比基准小的数放在右边
        return find(a, 0, n-1, K);
    }

    int find(vector<int>& a, int left, int right, int K)
    {
        int pivot = parti(a, left, right);

        if(pivot + 1 < K)
            return find(a, pivot+1, right, K);
        else if(pivot + 1 > K)
            return find(a, left, pivot-1, K);
        else
            return a[pivot];
    }

    int parti(vector<int>& a, int left, int right)
    {
        int tmp = a[left];

        int i=left;
        int j=right;
        while(i < j)
        {
            //从右边开始找到第一个比基准大的数的位置;
            //在下面的循环中若a[j] > tmp就会退出while循环,j就是位置;
            while(i < j && a[j] <= tmp)
            {
                j--;
            }
            //从左边开始找到第一个比基准小的数的位置;
            //在下面的循环中若a[i] < tmp就会退出while循环,i就是位置;
            while(i < j && a[i] >= tmp)
            {
                i++;
            }

            if(i < j)
            {
                //交换;
                int t = a[i];
                a[i] = a[j];
                a[j] = t;
            }
        }

        //首元素与基准交换;
        a[left] = a[i];
        a[i] = tmp;

        return i;
    }
};