（題目來(lái)源:力扣LeetCode)
題目：在未排序的數(shù)組中找到第?k?個(gè)最大的元素血当。請(qǐng)注意杀餐，你需要找的是數(shù)組排序后的第 k 個(gè)最大的元素广恢，而不是第 k 個(gè)不同的元素薯鼠。
示例 1:
輸入:[3,2,1,5,6,4] 和k = 2
輸出:5
題解：
方法一：冒泡排序 時(shí)間復(fù)雜度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;
????}
}
方法二：插入排序 時(shí)間復(fù)雜度O(N*N) 可以?xún)?yōu)化為（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;
????}
}
方法三：選擇排序 時(shí)間復(fù)雜度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;
????}
}
方法四：快速排序 時(shí)間復(fù)雜度O(N*logN)
（待優(yōu)化）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;
????}
}
