题解 | #寻找第K大# 做50%的快排

这道题说了用快排的思路去做。所以，如果把快排完整写一遍，整体不会有错。 但是它要求的是第K大，就要用到快排的有点，就是“部分排序”快速筛选。 所以，除了分出边界，左变排序、右边排序外， 可以针对K的值，选一侧继续排序。而舍弃另一边。这样O(n)应该理论上优化100%

import java.util.*;

public class Solution {
    public int findKth(int[] a, int n, int K) {
        quickSort(a, 0, a.length-1, K);
        
        //打印看一下，a不用全排序
        for(int i=a.length-1;i>0;i--){
            System.out.print(","+a[i]);
        }
        

        
        return a[K-1];
    }
    
    public void quickSort(int[] arr,  int begin,  int end, int K){
        
        int BEGIN = begin;
        int END = end;
          
        int pivot = arr[end];
        //System.out.println("pivot="+ pivot);
        while(end>begin){
            while(begin<end && arr[begin]>=pivot){
                //左侧疯狂占据地盘
                begin++;
            }
            while(begin<end && arr[end]<pivot){
                //右侧疯狂占据地盘
                end--;
            }
            if(end>begin){
                //指针停下的时候，旋转数据。重复上述。
                sw(arr, begin, end);
            }
        }
        
        //System.out.println("begin==end相遇begin="+begin+",end=" + end);
        
        //如果第K在一侧，则舍弃另一侧。
        if(BEGIN<begin && K-1<=begin-1){
            quickSort(arr, BEGIN, begin-1, K);
        }
        if(end<END && K-1>=end){
            quickSort(arr, end, END, K);
        }
        
        
    }
    
    //交换数据
    public void sw(int[] arr, int a, int b){
        if(a==b || arr[a]==arr[b]){
            return;
        }       
        arr[a]=arr[a]^arr[b];
        arr[b]=arr[a]^arr[b];
        arr[a]=arr[a]^arr[b];
        System.out.println("交换了"+arr[a] + "和" + arr[b]);
    }
}