给定一个数组A，要求找到数组A中第K大的数字。对于这个问题，解决方案有不少，此处我只给出三种：

方法1：

对数组A进行排序，然后遍历一遍就可以找到第K大的数字。该方法的时间复杂度为O(N*logN)

方法2：

利用简单选择排序法的思想，每次通过比较选出最大的数字来，比较上K次就能找出第K大的数字来。该方法的时间复杂度为O(N*K)，最坏情况下为O(N^2)。

方法3：

这种方法是本文谈论的重点，可以利用快排的思想，首先快排每次执行都能确定一个元素的最终的位置，如果这个位置是n-k(其中n是数组A的长度)的话，那么就相当于找到了第K大的元素。设确定的元素位置m的话，如果m > n - k大的话，那么第K大的数字一定在A[0]~A[m - 1]之间；如果m < n - k的话，那么第K大的数字一定在A[m+1]~A[n - 1]之间。
整个过程可以通过递归实现： 
class Solution {
    
    static int kk; // 第k大元素的快排后索引位置；
    
    public int findKthLargest(int[] nums, int k) {
        kk = nums.length - k; 
        quickSort(nums, 0, nums.length-1);     
        return nums[kk];
    }
    
    private void quickSort(int[] data, int start, int end){
        if(start < end){
            int mid = partition(data, start,end);
            //当第k大位置的数字归位时，结束递归遍历；
            if(mid == kk) return;
            else if(mid > kk) quickSort(data, start, mid-1); 
            else quickSort(data, mid+1, end);
            
        }
    }
    
    private int partition(int[] data, int start, int end ){
        int key = data[start];
        if(start > end) return -1;
        while(start < end){
            //一定要从后往前遍历！
            while(start < end && data[end] >= key) end--;
            if(start < end) swap(data, start, end);
            while(start < end && data[start] <= key) start++;
            if(start < end) swap(data, start, end);            
        }
        
        return start;
    }
    
    private void swap(int[] data, int i, int j){
        int tmp = data[i];
        data[i] = data[j];
        data[j] = tmp;
    }
}