YRB: https://www.cnblogs.com/yrbbest/p/4982861.html
grandyang: http://www.cnblogs.com/grandyang/p/4539757.html

方法1：quick-sort

思路：
使用快排的思想，取一个pivot，排序结束一遍pivot的位置就是它的order statistic。如果pivot的pos是k-1，可以直接返回pivot；如果pos>k - 1, 说明kth largest在左边，右边界向左推移；如果pos<k - 1, 说明kth largest在右边，左边界向右推移。

比如说k = 5，pivot = 6
index: 0··1··2··3··4··5··6··7··8
nums:[3, 4, 5, 2, 6, 8, 10, 7, 9]
`````````··············^···············
第一遍结果index(6) = 4, 下一步在[8, 10, 7, 9] 中寻找第1大、第0位的元素就好。

可以进来就k–，把order也转化成0-based，可以省点事。

Time Complexity - Amortized O(n)， worst case O(n2) Space Complexity - O(1)

From CLRS:

一刷自己写快排，太不整洁了，调了好久。放着引以为戒。

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        k--;
        return quickSort(nums, 0, nums.size() - 1, k);
    }
    
    
    int quickSort(vector<int> & nums, int start, int end, int k){
        if (start >= end) return nums[start];
        int pivot = nums[start];
        
        int slow = start;
        for (int fast = start + 1; fast <= end; fast++){
            if (nums[fast] >= pivot){
                swap(nums[slow + 1], nums[fast]);
                slow ++;
            }
        }
        swap(nums[start], nums[slow]);
        // compare slow with k
        if (slow == k)
            return nums[slow];
        else if (slow > k)
            return quickSort(nums, start, slow - 1, k);
        else 
            return quickSort(nums, slow + 1, end, k);
    }
};

下面这种是清晰的分成partion和找kth largest。partion部分整体很对称，比较好记。partitionCLRS是教科书的范式。主要的循环不变式在于：[start, i] 的元素，包括i本身，都要保持>=pivot。所以最后应该是和left本身交换而不是像教科书里和 i+1 交换。

class Solution1 {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int start = 0;
        int end = nums.size() - 1;
        
        while (true){
            // 本轮pivot最终的排位
            int pos = partition(nums, start, end);
            if (pos == k - 1) 
                return nums[pos];
            else if (pos > k - 1) 
            	end = pos - 1;
            else 
            	start = pos + 1;   
        }
    }
    
    int partition(vector<int>& nums, int start, int end){
        int pivot = nums[start], left = start + 1, right = end;
        
        while (left <= right){
            if (nums[left] < pivot && nums[right] > pivot){
                swap(nums[left++], nums[right--]);
            }
            if (nums[left] >= pivot) ++left;
            if (nums[right] <= pivot) --right;
        }
        // change with the pivot, which was set as the start
        swap(nums[start], nums[right]);
        return right;
    }

	int partitionCLRS(vector<int>& nums, int start, int end){
        int pivot = nums[start], left = start, right = start + 1;
        
        while (right <= end){
            if (nums[right] >= pivot){
                swap(nums[left + 1], nums[right]);
                left ++;
                right++;
            }
            else{
                right ++;
            }
        }
        swap(nums[start], nums[left]);
        return left;
    }
};

继续改进，implement shuffle(nums)，应该可以加快。

方法2:

用c++本身的sort

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        return nums[nums.size() - k];
    }
};

方法3:

用c++自带的pq

易错点：

1. c++的默认priority_queue是decreasing by default，这点和Java不一样
2. 不要pop过了，只要 k - 1次

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int> q(nums.begin(), nums.end());
        for (int i = 0; i < k - 1; ++i) {
            q.pop();
        }
        return q.top();
    }
};