题解 | #寻找第K大#

public class Solution {
    public static int ans;
    public int findKth(int[] a, int n, int K) {
        quick(a,0,n-1,K);
        return ans;
    }
    //快排模板
    void quick(int[] a,int l,int r,int K){
        if(l>r)return;
        int i=l,j=r,key=l;
        while(i<j){
        	//要注意，key选左边要从右边开始扫描，如果选右边要从左边开始扫描
            while(i<j&&a[j]>=a[l])j--;
            while(i<j&&a[i]<=a[l])i++;
            swap(a,i,j);
        }

        swap(a,i,l);
        //交换完之后判断该位置是否是第K大的位置
        if(i==a.length-K)
        {
            ans=a[i];return;//如果找到第K大的位置所在，直接返回
        }
        if(i>=a.length-K)quick(a,l,i-1,K);
        else quick(a,i+1,r,K);
    }
    void swap(int[] a,int i,int j){
        int t=a[i];
        a[i]=a[j];
        a[j]=t;
    }
}