在无序数组中求第K小的数

1）改写快排的方法(O(n) -> 概率期望)
2）bfprt算法O(n)
流程:
1.在无需数组中选一个数，大于这个数的放在数组右边，小于这个数的放在数组左边，等于这个数的放在数组中间。
2.比较第K小的数是够在等于区域，如果在那么直接返回此时的数就是第K小，如果给定的索引 > 等于区域那么递归进入右半部分继续前面过程，如果给定索引小于等于区域那么递归进入左半部分继续前面的过程直到找到第K小的数。

重点在于怎么在数组中找一个数来进行划分，可以利用随机快排的方法，在给定区间随机一个数，概率期望下的时间复杂度为O(n)。也可以利用bfptr算法，做到不是概率期望的O(n)

快排改进

public class Bfprt {

    public static int ksmall(int[] arr,int k){
        if(arr == null || k <= 0 || arr.length < k){
            // 表示没有
            return Integer.MIN_VALUE;
        }

        return bfprt(arr,0,arr.length-1,k -1);
    }

    // 在数组L R范围上返回第K小的数，并且index 一定在L .. R上
    private static int bfprt(int[] arr,int L,int R,int index){
        if(L == R){
            // 如果此时划分区间只有一个数，
            return arr[L];
        }
        // 在数组L -> R 中随机选一个数作为parttion的划分值，随机快排法
       // int num = L + ((int)(Math.random()*(R - L + 1)));
        // bfprt方法
        int num = midOfMid(arr, L, R);
        int[] parttion = parttion(arr, L, R, num);
        if(index >= parttion[0] && index <= parttion[1]){
            return arr[index];
        }else if(parttion[0] > index){
            // 左边
            return bfprt(arr,L,parttion[0]-1,index);
        }else{
            // 右边
            return bfprt(arr,parttion[1]+1,R,index);
        }

    }

    // 给定数组arr在L -> R范围上返回一个数作为划分值。
    // bfprt流程，把数组分为五个数一组，然后把这些组内部排序，
    // 在排好序的组中，每个组选一个中位数，如果最后一个组没有满，那么选择上
    // 中位数和下中位数都可以，然后在组成的中位数数组中选择中位数返回这个中位数，就是划分值
    private static int midOfMid(int[] arr,int L,int R){
        int line = 5;
        int of = (R - L + 1) % line == 0 ? 0 : 1;
        // 申请一个中位数数组，大小 (R - L + 1) / 5
        int len = (R - L + 1) / line + of;
        int[] midArr = new int[len];
        for(int i = 0;i < midArr.length;i++){
            int left = L + i*5;
            midArr[i] = insertSortAndGetMid(arr,left,Math.min(left + 4,R));
        }
        // 返回中位数数组的中位数
        return bfprt(midArr,0, midArr.length - 1,(midArr.length / 2));
    }

    // 排序
    private static int insertSortAndGetMid(int[] arr,int L,int R){
        if(L == R){
            return L;
        }
       // Arrays.sort(arr,L,R);
        insertSort(arr,L,R);
        return arr[L+((R - L) / 2)];
    }


    private static void insertSort(int[] arr,int L,int R){
        if(L == R){
            return;
        }
        int len = R - L + 1;
        for(int i = L;i <= R;i++){
            for (int j = i; j >=0 ; j--) {
                if((j-1 >= L) && arr[j] < arr[j-1]){
                    swap(arr,j,j-1);
                }
            }
        }
    }

    // 返回数组中等于arr[num]值得数下标范围
    private static int[] parttion(int[] arr,int left ,int right,int num){
        // 小于区域
        int L = left -1;
        // 大于区域
        int R = right + 1;
        int index = left;

        while (index < R){
            if(arr[index] < num){
                swap(arr,++L, index++);
            }else if(arr[index] > num){
                swap(arr,--R,index);
            }else {
                index ++;
            }
        }

        return new int[]{L+1,R-1};
    }

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

    public static void main(String[] args) {
        int[] arr = new int[]{3,4,1,2,6,5,90,8,9};
        int k = 3;
        System.out.println(ksmall(arr, k));
    }
}