寻找第K大（即排序）

这个题我的思路是排序再找到第K大的数，所以很多排序都能用，但是它要求时间复杂度为O（n）
1.简单冒泡排序（不符合本题要求）
时间复杂度为O（n2），两次循环；空间复杂度：O（1）
import java.util.*;

public class Solution {
public int findKth(int[] a, int n, int K) {
// write code here
if(a.length==0)//数组为空
return 0;
for(int i=0;i<n;i++){//冒泡排序
for(int j=0;j<n-i-1;j++){
if(a[j+1]>a[j]){//元素的后一个比其大就交换，即按大到小排序
int temp=a[j+1];
a[j+1]=a[j];
a[j]=temp;
}
}
}
return a[K-1];
}
}
2.运用库函数Arrays.sort
时间复杂度为：O（nlogn），空间复杂度：O（1）
import java.util.*;

public class Solution {
public int findKth(int[] a, int n, int K) {
// write code here
if(a.length==0)//数组为空
return 0;
Arrays.sort(a);//调用库函数
return a[n-K];
}
}
3.快排
平均时间复杂度为：O（nlog2）最坏时间复杂度为：O（n2），空间复杂度：O（1）
import java.util.*;

public class Solution {
public int findKth(int[] a, int n, int K) {
// write code here
if(a.length==0)//数组为空
return 0;
quick(a,0,n-1);
return a[n-K];
}
public void quick(int []a,int low,int high){//快排
if(low<high){
int mid=quickSort(a,low,high);
quick(a,low,mid-1);
quick(a,mid+1,high);
}
}
public int quickSort(int []a,int low,int high){
int temp=a[low];//基准元素
while(low<high){
while(low<high&&a[high]>=temp)//找到比基准元素小的元素
high--;
a[low]=a[high];
while(low<high&&a[low]<=temp)//找到比基准元素大的元素
low++;
a[high]=a[low];
}
a[low]=temp;
return low;
}
}
4.快排+二分的思想（从大到小排序）
时间复杂度：O（n），利用二分法不用全部排序；空间复杂度：O(1)
import java.util.*;

public class Solution {
public int findKth(int[] a, int n, int K) {
// write code here
if(a.length==0)//数组为空
return 0;
return quick(a,0,n-1,K);
}
public int quick(int []a,int low,int high,int K){
int mid=quickSort(a,low,high);
if(K==mid-low+1)//刚好是分组的中间元素
return a[mid];
else if(mid-low+1>K)//左边的个数大于K，表示在左边，递归左边
return quick(a,low,mid-1,K);
else//表示在右边，递归右边
return quick(a,mid+1,high,K-(mid-low+1));
}
public int quickSort(int []a,int low,int high){
int temp=a[low];//基准元素
while(low<high){
while(low<high&&a[high]<=temp)//找到比基准元素大的元素
high--;
a[low]=a[high];
while(low<high&&a[low]>=temp)//找到比基准元素小的元素
low++;
a[high]=a[low];
}
a[low]=temp;
return low;
}
}