一、题目描述
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1：
输入：nums = [3,2,1,5,6,4], k = 2
输出：5
示例 2：
输入：nums = [3,2,3,1,2,4,5,5,6], k = 4
输出：4
提示：
1 <= k <= nums.length <= 104
-104 <= nums[i] <= 104
二、题目解析
1、插入排序
class Solution {
public int findKthLargest(int[] nums, int k) {
insertSort(nums);
return nums[k - 1];
}
public void insertSort(int[] nums) {
for(int i = 1;i < nums.length;i++){
int target = nums[i];
int j = i - 1;;
for(;j >= 0;j--){
if(nums[j] < target){
nums[j+1] = nums[j];
}else{//找到第一个大于待排元素的元素
break;
}
}
//注意此处不能为nums[j+1] = nums[i]，因为在交换过程中nums[i]被改变
nums[j+1] = target;
}
}
}
2、快速排序思想1（一次扫描交换一个到目标位置）
左指针指向i=0，待排元素，（循环遍历前存储待排元素）
右指针指向j=length-1，最后一个元素。
从j位置往前遍历，找到大于待排元素，把该元素换到左指针指向位置（此时右指针位置废弃）；
从i位置往后遍历，找到小于待排元素，把该元素换到右指针指向位置（上轮的废弃位置；且此时左指针位置废弃，下一轮遍历将交换到该位置）；
再从j位置往前遍历，以此类推。
在此过程中，i走过的区域都是大于等于待排元素的，j走过的区域都是小于待排元素的，最后i和j相遇且指向的都是废弃元素。直接把待排元素排到这里即可。
class Solution {
public int findKthLargest(int[] nums, int k) {
quickSort(nums,0,nums.length - 1);
return nums[k-1];
}
public void quickSort(int[] nums,int start,int end){
//递归结束条件
if(start >= end){
return;
}
int mid = (start + end) / 2;
swap(nums,start,mid);
int index = partition(nums,start,end);
quickSort(nums,start,index - 1);
quickSort(nums,index + 1,end);
}
public int partition(int[] nums,int start,int end) {
int i = start,j = end;
int target = nums[start];
while(i < j){
while(nums[j] < target && i < j){
j--;
}
nums[i] = nums[j];
while(nums[i] >= target && i < j){
i++;
}
nums[j] = nums[i];
}
//最后return i或者j位置上的元素都可以，因为打破while的时候i==j
nums[j] = target;
return j;
}
public void swap(int[] nums,int i,int j){
int temp = nums[j];
nums[j] = nums[i];
nums[i] = temp;
}
}
3、快速排序思想2（一次扫描交换两个到目标位置）