BFPRT算法

心已赠人 2023-02-16 06:57 64阅读 0赞

### 一、先来看一个问题 ###

在一个乱序的数组中，寻找第k个小的值？

很多人第一种解法，用大顶堆，然后poll第k个就是答案了，但是时间复杂度是O（nlogn），有没有O（n）的算法呢？答案是肯定的，就是我们的BFPRT算法

### 二、铺垫 ###

这里我们需要大家知道荷兰国旗问题的解法，也就是选定一个基值，比它小的放在左边，比它大的放在右边，相等的放在中间，其实就是快速排序的partition过程。数组\{5,7,12,4,2,7,2,5,6,0,1,2\}，假设选定基值是6，那么数组表示

![20200609120848690.png][]

这样实际就是一个荷兰国旗，这个时候我们保存中间6的左边界l和右边界r，判断 k-1 是否在l 和 r是否在中间，如果在就说明是6了，等于中间的值。如果不是，判断大小选择左边数组继续递归还是右边的数组继续递归。这样就可以一直找到这个值了。这种时间复杂度O（n），这种是基于概率的时间复杂度的一个期望。

考虑一种极端情况，如果每一次找出的值，都是没有右边只有左边，假设样本n，T（n）= T(n - 1) + n。那么时间复杂度就是O（n2）。实际上就失去了意义，说来说去还是这个基准值6怎么来找？如果我们能够保证每次找到基准值的左右两边数组的长度近似相等，那么就可以达到O（n）,同时这种方法是稳定的，不是基于概率的，**我们的BFTRP算法就是用来找到这个基准值的。**

### **三、上菜** ###

**1、小小的分析**

比如现在有：arr = \[1,2,4,1,2,5,7,3,21,7,3,1,6,,0,6,3,1,34,65,62,2,1,5,7,10\]，这样一个数组。

我没分为五个一组（如果剩余的数不够5，那么单独成一组）：

![20200609124309364.png][]

对每一个数组进行排序，每个数组里面有5个数，是常数长度，那么时间复杂度O（1），因为有n/5，所以时间复杂度还是O（n）。注意这个排序只跟小组内部有关，跟数组之间没有关系。排序后就是这个熊样子

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70][]

然后取中位数，形成一个新数组：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 1][]

新数组\[2,7,3,34,5\]。然后我们还是用这种方式以5个为一组进BFTRP，只不过现在寻找的k变成了新数组长度的中间位置数，很好理解，现在要找中位数，那么就是第中间位置小的数，就是中位数了。在这个例子中，我们找到中位数7，然后就以7为基准值，比它小的放左边........。然后看要找的k是否在中间区域，如果在，直接返回7，如果不在向左边或者右边递归。

我们来看一下，为什么这个能够达到O（n），因为比如刚开始数组为n，那么五个为一组就有n/5个数组，那么这些个数组会拿出中位数组成new int\[n/5\]这么大的数组，有n/5个数，这些个数的中位数中大于等于该中位数的有n/10个，就是n/（5\*2），n/10，这些数，在原来的数组中有3个大于等于中位数的数，所以就是至少有3n/10个数大于你要找到的中位数，那么也就是最多有7n/10个数小于中位数的，所以可以保证不会出现上面极端情况。

时间复杂度 T(N) = T(N/5) + T(7N /10) + O(N)。最后通过计算（算法导论第九章）时间复杂度O（n）。

**实际上最重要的就是找到基准值，一个中位数**

**2、代码**

public static void main(String[] args) {
            int[] arr = { 6, 9, 1, 3, 1, 2, 2, 5, 6, 1, 3, 5, 9, 7, 2, 5, 6, 1, 9 };
            System.out.println(getMinKthByBFPRT(arr,10));
    
        } 
       /**
         * 获得第k小的数
         */
        public static int getMinKthByBFPRT(int[] arr, int K) {
            return select(arr, 0, copyArr.length - 1, K - 1);
        }

main函数调用这个方法，传入数组，开始位置、结束位置，以及要查找的下标。

/**
         * bftrp 寻找中位数。
         */
        public static int select(int[] arr, int begin, int end, int 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 select(arr, begin, pivotRange[0] - 1, i);
            } else {
                return select(arr, pivotRange[1] + 1, end, i);
            }
        }

select方法就是BFTRP算法核心内容

（1）如果寻找的数组开始和结束位置一样，那么直接返回

（2）medianOfMedians获取中位数，也就是我们的基准值。

（3）以这个基准值整理数组，比它小的在左边，比它大的在右边，相等的在中间。

（4）pivotRange\[0\]表示中间基准值的左边界，pivotRange\[1\]表示中间基准值的右边界，如果在这之内直接返回，否则向左边或者右边递归调用。

/**
         * 中位数数组作为划分值，求中位数数组的中位数
         */
        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 select(mArr, 0, mArr.length - 1, mArr.length / 2);
        }

获取中位数，就是上边说的以5个为一组排序，然后或者每组的中位数，然后再次调用BFTRP算法，只不过查找的中间变成了数组的中间位置，这个值就是中位数！！！最后是可以返回到上面的。然后操作。

/**
         * 获取中位数
         */
        public static int getMedian(int[] arr, int begin, int end) {
            insertionSort(arr, begin, end);
            int sum = end + begin;
            int mid = (sum / 2) + (sum % 2);
            return arr[mid];
        }
    
        /**
         * 排序小数组
         */
        public static void insertionSort(int[] arr, int begin, int end) {
            for (int i = begin + 1; i != end + 1; i++) {
                for (int j = i; j != begin; j--) {
                    if (arr[j - 1] > arr[j]) {
                        swap(arr, j - 1, j);
                    } else {
                        break;
                    }
                }
            }
        }
    
        public static void swap(int[] arr, int index1, int index2) {
            int tmp = arr[index1];
            arr[index1] = arr[index2];
            arr[index2] = tmp;
        }

排序获取中位数代码！！

/**
         * 以pivotValue为中心，比他小的放左边，比他大的放右边
         * 返回一个两个元素的数组，0位置是中间数的左边，1位置是中间数的右边
         */
        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;
        }

partition其实就是荷兰国旗那段代码。

最后就得到答案了。

[20200609120848690.png]: https://img-blog.csdnimg.cn/20200609120848690.png
[20200609124309364.png]: https://img-blog.csdnimg.cn/20200609124309364.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200609124734161.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200609124814610.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70