有两种解决思路：
1）堆排序，时间效率上堆更快
2）快排分区减治法，第一次分区，若k在左边，则去左分区找，在右边则去右分区找，每次分区
区间均会减小
第一次排序为整个数组，为 n，第二次为 n/2，最后为 1，
然后相加 n+n/2 + n/4 + ....+ 1，这是个等比数列，和为 2n -1，所以复杂度为 O(n)
// 快排解决方法
func findKthLargest(nums []int, k int) int {
l := 0
r := len(nums)
index := r - k // index位元素
for {
p := partition(nums, l, r)
if index == p {
return nums[p]
} else if index < p { // value在[l...p)里面
r = p
} else { // value在[p+1...r)里面
l = p + 1
}
}
}
func partition(nums []int, l, r int) int {
v := nums[l]
less := l
for i := l + 1; i < r; i++ {
if nums[i] < v {
less++
nums[less], nums[i] = nums[i], nums[less]
}
}
nums[less], nums[l] = nums[l], nums[less]
return less
}
提交leetcode，测试通过
