分治法求第k大元

核心是类似于快速排序的划分过程
代码如下：

public static int quickSelect(int[] arr,int lo,int hi,int k){
        if(lo>hi) return Integer.MAX_VALUE;
        if(lo==hi&&k==1) {
            System.out.println("lo==hi");
            return arr[lo];
        }
        int key=arr[lo];
        int i=lo;
        int j=hi;
        while(i<j){
            while(i<j&&arr[j]>=key){
                j--;
            }
            arr[i]=arr[j];
            while(i<j&&arr[i]<=key){
                i++;
            }
            arr[j]=arr[i];
        }
        arr[j]=key;
//      System.out.println("log i:"+i);
//      System.out.println("log j:"+j);
        //return i or j;
        if(k<i+1){
            return quickSelect(arr,lo,i-1,k);
        }else if(k>i+1){
            return quickSelect(arr,i+1,hi,k);//仍然是k
        }else {
            System.out.println("k==i+1");
            return arr[i];
        }
        
    }

我在该段过程浪费了很多时间：

else if(k>i+1){
            return quickSelect(arr,i+1,hi,k);//仍然是k

之前我写成了

return quickSelect(arr,i+1,hi,k-i-1);

理解成是右边数组的第k-i-1个元素，思路正确，但是传递的参数不同，因为仍然是以整个原数组作为参照系的。
该代码只有一次递归调用，所以子问题的个数为1,分解合并代价为O(N),根据主定理，平均运行时间为O(N).