class Solution {
    public int findKthLargest(int[] nums, int k) {
    	// 方法一 直接调库快排 AC了
        // Arrays.sort(nums);
        // return nums[nums.length-k];
        
        // 方法二 手写了一个快排 就超时了？？ 也不是很懂
        return quickSort(nums,0,nums.length-1)[nums.length-k];
        
        }
    
    public int[] quickSort(int[] nums,int _left,int _right) {
        int left = _left;
        int right = _right;
        int tmp = 0; //基准数
        if(left <= right) {
            while(left != right) {
                tmp = nums[left];
                while(left < right && nums[right] > tmp)
                    right --;
                nums[left] = nums[right];
                while(left < right && nums[left] < tmp)
                    left ++;
                nums[right] = nums[left];
            }
        }
        nums[right] = tmp;
        quickSort(nums,_left,left-1);
        quickSort(nums,right+1,_right);
        return nums;
    }
}