leetcode O(n)找数组中第k个最大的元素，利用的是类似快速排序的写法，涉及到 Hoare 划分
原文链接：https://www.cnblogs.com/Time25/p/20241793.html
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public:
//这个快速选择算法，平均来说，是N+N/2+N/4.....到最后是2*N，也就是O(N)
//但是，如果是一个倒序的数组的话，那么还是最复杂的N^2
//这个写法中的严格小于是关键，可以应对多个复杂元素
//比如 1 1 1 1 ，如果是<=,>=的话，会把所有元素都划分到一边，然后复杂度还是N^2
int quickselect(vector<int>&nums,int l,int r,int k){
if(l==r)return nums[k];//这里返回k的原因是，函数里面传入的参数是n-k，这个直接返回nums[k]
//就是nums[n-k]了，因为传入的这个k就是n-k
int par=nums[l],i=l-1,j=r+1;
while(i<j){
do i++; while(nums[i]<par);
do j--; while(nums[j]>par);
if(i<j)swap(nums[i],nums[j]);
}
//if(j<=k)return quickselect(nums,j,r,k);
//else return quickselect(nums,l,j-1,k);
/**
* 这里，上下两种写法，看起来是一样的，但是，你这样写就会超时，举个例子
* [2,1]数组，要找的是第0个元素，也就是传入的参数k是0
* 交换后是[1,2]，结束后j=0，j=0 <= k=0,
* 然后就会调用quickselect(nums,0,1,k),你会发现，本来就是调用quickselect(nums,0,1,k)
* 你现在用调用了一次，那不就又是原来那个吗，那递归调用就会一直进行，永远没有结束，
*/
if (k <= j)
return quickselect(nums, l, j, k); // 严格对应左区间 [l, j]
else
return quickselect(nums, j + 1, r, k); // 严格对应右区间 [j + 1, r]
}
//就是O(n)找到倒数第k个的数字，在这个数组中
int findKthLargest(vector<int> &nums, int k) {
int n = nums.size();
return quickselect(nums, 0, n - 1, n - k);
}
};
这里的划分是 Hoare 划分，不可以微调！！不可以微调！！
