（题目来源:力扣LeetCode)
题目：在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:
输入:[3,2,1,5,6,4] 和k = 2
输出:5
题解：
方法一：冒泡排序 时间复杂度O（N*N）
class Solution {
public int findKthLargest(int[] nums, int k) {
if(nums.length==0 || k==0){
return 0;
}
sort(nums,k);
return nums[k-1];
}
public void sort(int [] nums,int k){
int n=nums.length;
for(int i=n-1;i>0;i--){
for(int j =0;j<i;j++){
if(nums[j]<nums[j+1])
swap(nums,j,j+1);
}
}
}
public void swap(int [] nums,int x,int y){
int temp = nums[x];
nums[x]=nums[y];
nums[y]=temp;
}
}
方法二：插入排序 时间复杂度O(N*N) 可以优化为（O（N*logN）)
class Solution {
public int findKthLargest(int[] nums, int k) {
if(nums.length==0 || k==0){
return 0;
}
InsertSort(nums,k);
return nums[k-1];
}
public void InsertSort(int [] nums,int k){
int n=nums.length;
for(int i=1;i<n;i++){
for(int j=i;j>0;j--){
if(nums[j]>nums[j-1]){
swap(nums,j,j-1);
}
}
}
}
public void swap(int [] nums,int x,int y){
int temp = nums[x];
nums[x]=nums[y];
nums[y]=temp;
}
}
方法三：选择排序 时间复杂度O（N*N）
class Solution {
public int findKthLargest(int[] nums, int k) {
if(nums.length==0 || k==0){
return 0;
}
SelectionSort(nums,k);
return nums[k-1];
}
public void SelectionSort(int [] nums,int k){
int n=nums.length;
for(int i=0;i<n-1;i++){
int maxPos = i;
for(int j = i+1;j<n;j++){
if(nums[maxPos]<nums[j])
maxPos=j;
}
swap(nums,maxPos,i);
}
}
public void swap(int [] nums,int x,int y){
int temp = nums[x];
nums[x]=nums[y];
nums[y]=temp;
}
}
方法四：快速排序 时间复杂度O(N*logN)
（待优化）class Solution {
public int findKthLargest(int[] nums, int k) {
if(nums.length==0 || k==0){
return 0;
}
sort(nums,0,nums.length-1);
return nums[nums.length-k];
}
public void sort(int [] nums,int leftBound,int rightBound){
if(leftBound>=rightBound)return;
int mid = Position(nums,leftBound,rightBound);
sort(nums,leftBound,mid-1);
sort(nums,mid+1,rightBound);
}
public int Position(int [] nums,int leftBound,int rightBound){
int pivot= nums[rightBound];
int left=leftBound;
int right=rightBound;
while(left<right){
while(left<right && nums[left]<pivot) left++;
while(left<right && nums[right]>pivot) right--;
if(left<right)swap(nums,left,right);
}
if(pivot<nums[left]){
swap(nums,rightBound,left);
}
return left;
}
public void swap(int [] nums,int x,int y){
int temp = nums[x];
nums[x]=nums[y];
nums[y]=temp;
}
}
