BFPRT算法

public static int getMinKthByBFPRT(int[] arr,int k) {
    int[] copyArr = new int[arr.length];
    copyArr = copyArray(arr);
    return bfprt(copyArr,0,copyArr.length - 1,k - 1);
}
    
public static int[] copyArray(int[] arr) {
    int[] tmp = new int[arr.length];    
    for(int i = 0;i != arr.length;i++) 
        tmp[i] = arr[i];
    return tmp;
}
    
public static int bfprt(int[] arr,int begin,int end,int i) {//begin到end范围内求第i小的数
    if(begin == end)
        return arr[begin];
    int pivot = medianOfMedians(arr,begin,end);//中位数作为划分值
    int[] pivotRange = partition(arr,begin,end,pivot);//进行划分，返回等于区域
    if(i >= pivotRange[0] && i <= pivotRange[1]) 
        return arr[i];
    else if(i < pivotRange[0])
        return bfprt(arr,begin,pivotRange[0] - 1,i);
    else 
        return bfprt(arr,pivotRange[1] + 1,end,i);
}
    
public static int medianOfMedians(int[] arr,int begin,int end) {
    int num = end - begin + 1;
    int offset = num % 5 == 0 ? 0 : 1;
    int[] mArr = new int[num / 5 + offset];
    for(int i = 0; i < mArr.length;i++) {
        int beginI = begin + i * 5;
        int endI = beginI + 4;
        mArr[i] = getMedian(arr,beginI,Math.min(end,endI));
    }
    return bfprt(mArr,0,mArr.length - 1,mArr.length / 2);
}
    
public static int getMedian(int[] arr,int begin,int end) {
    Arrays.sort(arr,begin,end);
    int sum = end + begin;
    int mid = (sum / 2) + (sum % 2);
    return arr[mid];
}
    
public static int[] partition(int[] arr,int begin,int end,int pivotValue) {
    int small = begin - 1;
    int cur = begin;
    int big = end + 1;
    while(cur != big) {
        if(arr[cur] < pivotValue)
            swap(arr,++small,cur++);
        else if(arr[cur] > pivotValue)
            swap(arr,cur,--big);
        else 
            cur++;
    }
    int[] range = new int[2];
    range[0] = small + 1;
    range[1] = big - 1;
    return range;
}

public static void swap(int[] arr,int i,int j) {
    int t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
}