题目：
在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
说明:
你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。
分析：
查找未排序的数组，找到第k个最大的元素。
最简单的做法应该就是对数组进行排序，然后遍历拿到第k个最大元素。那么此时这道题就是一道排序题了。
但是如果是这样的话，这道题就没有必要了。应该有其他解法，不需要进行排序就可以搞定。
因为要取的是第k个，所以感觉不需要进行完全排序即可。
这个时候想起来快速排序。快速排序的特点是先找一个基准，让大于这个基准的放在一边（命名为Array），小于这个基准的放在领一边。
- 如果Array个数是k-1，那么这个基准就正好是第k个。
- 如果Array个数大于k-1，说明第k大元素还是在左边，继续对左边进行重复操作
- 如果Array个数小于k-1，说明第k大元素在右边数组里，要对右边的数组进行重复操作。
class Solution:
def quickSort(self,left,right,nums,k) :
head,trail,temp = left,right,nums[left]
if head >= trail:
return nums[trail]
#大的放在左边，小的放在右边
while head < trail:
while head < trail and nums[trail] <= temp:
trail -= 1
nums[head] = nums[trail]
while head < trail and nums[head] >= temp:
head +=1
nums[trail] = nums[head]
nums[head] = temp
if head-left == k-1: # 判断是否head就是第k个元素
return temp
elif head-left > k-1: # 说明第k大元素在左边
return self.quickSort(left,head-1,nums,k)
else: # 说明第k大元素在右边 此时需要重新计算k（这个位置是重点）
return self.quickSort(head+1,right,nums,k-head-1+left)
def findKthLargest(self, nums: List[int], k: int) -> int:
return self.quickSort(0,len(nums)-1,nums,k)
