The idea is to use modified quick sort. We know the key point of quick sort is to divide the array into two parts, one is smaller than(or equal to) the pivot value, and the other half bigger than it(or equal).

The modified version is we only sort the part if the kth element is within it. Let's say we know the kth biggest element should appear at the index array[n-k] (where n is the size), and each time when we divide the array into two parts by using the pivot value, we check the range of each part, if index [n-k] is not within the range we won't sort it.

And to increase the chance of dividing the array into two parts of equal length I choose the pivot which is the median among start, end and mid element.

public class Solution {

public int findKthLargest(int[] nums, int k) {

int n = nums.length;

int target = n - k;

quicksort(nums, 0, n-1, target);

return nums[n-k];

}

```
private void quicksort(int[] nums, int start, int end, int target){
if(start >= end){
return;
}
int mid = start + (end - start)/2;
int pivot = choosePivot(nums[mid], nums[start], nums[end]);
//int pivot = nums[mid];
int i = start;
int j = end;
while(i <= j){
while(nums[i] < pivot){
i++;
}
while(nums[j] > pivot){
j--;
}
if(i <= j){
if(nums[i] != nums[j]){
swap(nums, i, j);
}
i++;
j--;
}
}
if(target <= i - 1){
quicksort(nums, start, i - 1, target);
}
else{
quicksort(nums, i, end, target);
}
}
private int choosePivot(int a, int b, int c){
if(a > b){
if(c > a){
return a;
}
else if(c > b){
return c;
}
else{
return b;
}
}
else{
if(c > b){
return b;
}
else if(c > a){
return c;
}
else{
return a;
}
}
}
private void swap(int[] nums, int i, int j){
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
```

}