BFPRT算法：求第K小或者第K大的数

问题：

一个数组中求第k小或者第k大的数

思路（转自http://blog.csdn.net/liuxiao214/article/details/78597508）：

不通过排序求第k小的数，时间复杂度为O(N)。

主要是利用快排中的partition过程。

1、找到一个划分值，按照partition的过程，分为小于区、等于区、大于区，则可知等于区是在整个数组有序后不变的部分。

2、求第K小的数，就是数组有序后下标为k-1的数。

3、所以，如果等于区包含这个k-1，则等于区的数就是第k小的数，直接返回。否则，继续partition过程。

BFPRT的思想是对划分值的选择进行优化，不再是随机选取划分值，而是通过这样一个过程：

1、将数组分为5个一组，不足5个的自动成一组。划分组所用时间为O(1)。

2、将每个组进行组内排序，可用插入排序。因为排序只有5个数，时间复杂度可记为O(1)，所有组都排序为O(N)。

3、得到每个组内的上中位数，然后将这些上中位数组成新的数组mediums。

4、求出mediums数组中的上中位数pvalue，不使用排序，用的是递归调用BFPRT的过程，求上中位数就是求mediums数组第mediums.size()/2小的数。

5、此时得到的pvalue就是选取的划分值，然后进行partition过程即可。

为什么要这样选取划分值，这是因为，假设数组长度为n，则mediums数组的长度为n/5，则得到的pvalue在medium中会有n/10的数比其小，而这n/10的数，在自己的5个数的小组中，又会有3个数比pvalue小，所以，至少有n/10*3即3n/10个数比pvalue小，至多有7n/10个数比pvalue大，可以确定的淘汰掉3n/10的数。这样划分比较均衡。

6、刚才拿到pvalue划分值之后，进行partition过程，会返回等于区的边界下标。

7、如果k在等于的范围内，则返回pvalue；k在等于区的左边，则递归调用左边小于区的部分；k在等于区的右边，则递归调用大于区的部分。

代码：

public static int[] getMinKNumsByBFPRT(int[]arr,int k){
        if (k<1||k>arr.length){
            return arr;
        }

        int min = getMinKthByBFPRT(arr,k);
        int[] help = new int[k];
        int index = 0;
        for (int i =0;i<arr.length;i++){
            if (arr[i]<min)
            help[index++] = arr[i];
        }
        for (;index<help.length;index++){
            help[index] = min;
        }
        return help;
    }

    public static int getMinKthByBFPRT(int[] arr,int k){
        int[] cArr = copyArray(arr);
        int m = select(cArr,0,cArr.length-1,k-1);
        return m;
    }

    public static int[] copyArray(int[] arr) {
        int[] res = new int[arr.length];
        for (int i = 0; i != res.length; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    public static int select(int[] arr,int begin,int end,int i){
        if (begin==end){
            return arr[begin];
        }

        int p = mediaOfMedia(arr,begin,end);
        int[] pArr = partition(arr,begin,end,p);
        if (i>=pArr[0]&&i<=pArr[1]){
            return arr[i];
        }else if (i<pArr[0]){
            return select(arr,begin,pArr[0]-1,i);
        }else {
            return select(arr, pArr[1] + 1, end, i);
        }
    }

    //获取等于区的数
    public static int mediaOfMedia(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] =  getMedia(arr,beginI,Math.min(endI,end));
        }
        return select(mArr,0,mArr.length-1,mArr.length/2);
    }

    //partition过程
    public static int[] partition(int[] arr,int l,int r,int m){
        int less = l-1;
        int more = r+1;
        int cur = l;

        while (cur<more){
            if (arr[cur]>m){
                swap(arr,--more,cur);
            }else if (arr[cur]<m){
                swap(arr,++less,cur++);
            }else {
                cur++;
            }
        }
        return new int[]{less+1,more-1};
    }

    //获取中位数
    public static int getMedia(int[] arr,int begin,int end){
        insertSort(arr,begin,end);
        int sum = begin + end;
        int mid = (sum/2) + (sum%2);
        return arr[mid];
    }

    //插入排序
    public static void insertSort(int[] arr,int begin,int end){
        //有begin end 做想定条件的时候注意循环条件
        for (int i = begin+1;i<end+1;i++){
            for (int j = i -1;j>=begin&&arr[j]>arr[j+1];j--){
                swap(arr,j,j+1);
            }
        }
    }

    public static void swap(int[] arr, int index1, int index2) {
        int tmp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = tmp;
    }