一、先来看一个问题

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

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

二、铺垫

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

这样实际就是一个荷兰国旗，这个时候我们保存中间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，那么单独成一组）：

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

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

新数组[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其实就是荷兰国旗那段代码。

最后就得到答案了。