寻找第K大

快速排序：每次移动，可以找到一个标杆元素，然后将大于它的移到左边，小于它的移到右边。然后分别对左边和右边进行排序，不断划分左右子段，直到整个数组有序。放到这道题中，如果标杆元素左边刚好有K-1个比它大的，那么该元素就是第K大，如果它左边的元素比K - 1多，说明第K大在其左边，直接二分，不用管标杆元素右边，同理如果它左边的元素比K-1少，那第K大在其右边，左边不用管。

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.

 public int findKth(int[] a, int n, int K) {
        // write code here
        return quicksort(a,0,n-1,K);

    }

    public int quicksort(int[] a,int l,int r,int k){
        int p=partion(a,l,r);

        if(p==a.length-k){
            return a[p];
        }else if (p>a.length-k){
            return quicksort(a,l,p-1,k);
        }else {
            return quicksort(a,p+1,r,k);
        }

    }

    public int partion(int[] a,int l,int r){
        int temp=a[l];
        while (l<r){
            while (l<r&&a[r]>=temp) r--;
            a[l]=a[r];
            while (l<r&&a[l]<=temp) l++;
            a[r]=a[l];
        }
        a[l]=temp;
        return l;
    }