第k大的元素

堆排序，创建一个大小为k的小顶堆

int findKthLargest(vector<int>& nums, int k) {

        vector<int> mat(k);
        for(int i=0;i<k;i++)
            mat[i]=nums[i];
        //从下往上调整堆
        for(int i=k/2-1;i>=0;i--)
            adjust(mat,i,k);
        for(int i=k;i<nums.size();i++)
        {
            if(nums[i]>mat[0])
            {
                mat[0]=nums[i];
                adjust(mat,0,k);
            }
            
        }
        return mat[0];
    }
void adjust(vector<int> &a,int m,int t)
    {
        for(int k=2*m+1;k<t;k=2*k+1)
        {
            if(k+1<t&&a[k+1]<a[k])
                k++;
            //k指向较小的元素
            if(a[k]<a[m])
            {
                swap(a[k],a[m]);
                m=k;
            }
            else
                break;
        }
    }
void swap(int &a,int &b)
    {
        int c=a;
        a=b;
        b=c;
    }

快速排序，右边有k个较大的元素

 int findKth(vector<int> &a, int n, int K) 
{
	return quick(a, 0, n - 1, n-K);
}
int quick(vector<int>& a, int l, int r, int K)
{
	int temp = a[l];
	int left = l; int right = r;
	while (l < r)
	{
		while (l<r&&a[r]>temp)
			r--;
		if (l < r)
			a[l++] = a[r];
		while (l < r&&a[l] < temp)
			l++;
		if (l < r)
			a[r--] = a[l];
	}
	a[l] = temp;
	if (l == K)    return temp;
	else if (l > K)
		return quick(a, left, l - 1, K);
	else
		return quick(a, l + 1, right, K);

}