题目链接：215. Kth Largest Element in an Array
题目大意：给定无序数组求第k大，经典面试题
题目思路：利用快速排序，每次定一个轴，比轴大的放左边，小的放右边，如果左边的数量小于k，则第k大在右边，反之在左边，每次去找就好了
时间复杂度&&空间复杂度：O（n）（需要找的总共次数为n/2+n/4+…+1 = 2n-1次）&&O（1）
class Solution { public: int findKthLargest(vector<int>& nums, int k) { int left = 0,right = nums.size(); while(true){ int pos = partition(nums, left, right); if(pos == k-1) return nums[pos]; if(pos > k-1) right = pos; else left = pos+1; } } int partition(vector<int>& nums,int left,int right){ int pivot = left,l = left,r = right; while(l < r){ while(++l < right&&nums[l] >= nums[pivot]); while(--r > left&&nums[r] <= nums[pivot]); if(l < r) swap(nums[l],nums[r]); } swap(nums[pivot],nums[r]); return r; } };