方法一：使用语言自带的 sort

开始看到这个题目的时候，我惊呆了，这难道不是一个简单题吗？不直接使用语言自带的排序不就可以了吗？试了下，发现居然可以提交成功！惊呆了。

有些时候，在写业务场景的时候，如果数据量不大的情况，使用这种最简单的方案是“性价比”最高的，但如果数据量有很大的时候，需要考虑下怎么进行优化。

方法二：快速排序

网上关于快速排序肯定已经有好多方法了，下面说下我理解的快速排序。

1. 找一个基准数（可以是随机的，也可以是数组第一个 or 最后一个元素）。
2. 遍历数组，将比 基准数 小的元素放在基准数的左边，将比 基准数 大的元素放在基准数的右边。
3. 再分别对左边和右边的元素进行 步骤1 和 步骤2 操作（递归）。
4. 直到 left === right（每一个最小的数组只有一个元素），就代表排序完成
5. 对于本题，因为是要找到第 K 个最大元素，那么其实不需要将数组全部进行排序，只需要找到第 K 个最大元素就可以，那么就可以提前终止排序。在找到 基准数 索引为 length - k 的时候，改数就是要找的第 K 个最大元素。
6. 在步骤 2 中，直接使用移动就可以，降低空间复杂度。
7. 我们在操作的时候可以直接使用 index，不对其值进行操作。知道了 index，也就有了最后排序的结果。

class FindKthLargest {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int target = nums.size() - k;
        int left = 0;
        int right = nums.size() - 1;
        while (true){
            // 找出最左边元素的 index
            int index = partition(nums, left, right);
            if(index == target){
                return nums[index];
            } else if(index < target){
                // 如果目标元素在基准数右边（大于基准数），将数组缩短
                left = index + 1;
            } else {
                right = index - 1;
            }
        }
    }
    int partition(vector<int>& nums, int left, int right){
        // 选取最左侧元素为 基准数，pivot 为 基准数的值，j 为基准数的 index
        // 先不对基准数进行移动，j 记录小于基准数的个数
        // 如果遍历的数大于基准数，不进行移动（因为基准数在最左边）
        // 如果遍历的数小于基准数，进行移动
        int pivot = nums[left];
        int j = left;
        for(int i = left + 1; i <= right; i++){
            if(nums[i] < pivot){
                // 小于 pivot 的元素都被交换到前面
                j++;
                if(i != j){
                    nums = swap(nums, j, i);
                }
            }
        }
        // 最后，已经知道了基准数的位置，将基准数移动到对应的位置（基准数最开始的位置为最左边，因为没有进行移动，最后的位置为 j）
        nums = swap(nums, j, left);
        return j;
    }
private:
    vector<int> swap(vector<int> nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
        return nums;
    }
};

方法三：基于堆排序的选择方法