题目：

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例：

image.png

思路：

先排序，然后返回数组的倒数第k位（数组长度-k）
排序的思路：
1.Arrays.sort(array)
2.快速排序

代码：

class Solution {

    public int Partition(int[] nums, int low, int high) {
        int povit = nums[low];
        while (low < high) {
            while (low < high && nums[high] >= povit) {
                high --;
            }
            nums[low] = nums[high];
            while (low < high && nums[low] <= povit) {
                low ++;
            }
            nums[high] = nums[low];
        }
        nums[low] = povit;
        return low;
    }
    public void QSort(int[] nums, int low, int high) {
        if (low < high) {
            int povitIndex = Partition(nums, low, high);
            QSort(nums, low, povitIndex - 1);
            QSort(nums, povitIndex + 1, high);
        }
    }
    public int findKthLargest(int[] nums, int k) {
        int index = nums.length - k;
        QSort(nums, 0, nums.length - 1);
        return nums[index];
    }
}

时间复杂度：
快速排序 O(n)，空间复杂度：O(1)
Arrays.sotr()排序 O(nlogn)，空间复杂度：O(1)