题目：
求出数组中第K大元素（指数组排序后的第K大的元素，不是第K个不同的元素）
解题思路：
本题的解法采用类似快速排序的分治算法。
在快排算法中，我们需要选择一个pivot元素并将数组分为三个部分：大于pivot，等于pivot，小于pivot。
我们通常使用快排来进行从小到大的排序，但现在只需要对代码稍微做一些修改就能够进行从大到小的排序，将比pivot大的元素放在pivot左边，将比pivot大的元素放在pivot的右边。因此，如果pivot在数组的第 k-1 位，那么pivot就是整个数组的第K大元素；如果pivot的位置在第 k-1 位的右边，那么就在pivot的左边部分继续寻找第K大元素；如果pivot的位置在第 k-1 位的左边，那么就在pivot的右边部分继续寻找第K大元素。
代码：
class Solution { public: int partition(vector<int>& nums, int left, int right){ int l = left + 1, r = right; int pivot = nums[left]; while(l <= r){ if(nums[l] < pivot && nums[r] > pivot){ swap(nums[l], nums[r]); l ++; r --; } if(nums[l] >= pivot) l ++; if(nums[r] <= pivot) r --; } swap(nums[r], nums[left]); return r; } int findKthLargest(vector<int>& nums, int k) { int left = 0; int right = nums.size() - 1; while(1){ int pos = partition(nums, left, right); if(pos == k - 1) return nums[pos]; if(pos > k - 1) right = pos - 1; else left = pos + 1; } } };算法分析：
平均情况下，一个问题的大小被减小到原来的一半，因此可以写出递推公式T(n) = T(n/2) + O(n)，其中O(n)是partition所用的时间。根据大师定理可以求出算法的时间复杂度为O(n)。
在最坏情况下，递归公式就变成了T(n) = T(n-1) + O(n)，时间复杂度为O(n^2)。
相比之下，本题算法只需要处理partition之后其中的一半，快排则需要处理两边的数，因此快排的递推公式是T(n) = T(n/2) + O(n)，由大师定理可得时间复杂度为O(nlogn)。
