提示：bfprt算法在算法界的地位极其高，要搞懂它的核心思想！
今天咱们先学bfprt算法的核心基础知识，方便下一篇咱们透彻理解什么事bfprt算法
重要的基础知识：【1】10大排序算法之五：快排算法，快速排序【不稳定】，复杂度中，系统常用快速排序
【2】递归思想求arr中最大值，递归函数先调用处理几部分，然后整理和归并信息返回
文章目录
- Topk问题：bfprt算法预备知识： 无序数组arr，找出如果arr有序的话，第k小那个数是多少？
- @[TOC](文章目录)
- 啥是bfprt算法，它干嘛的？
- 一、审题
- 暴力解：用系统排序之后，直接获取k-1下标那个数
- bfprt的基础重点是荷兰国旗问题partition
- 笔试AC解：靠概率累加和凑运气，快速排序但只进一边
- 非bfprt方法：概率累加和手撕代码
- 那bfprt算法怎么搞呢？
- 总结
解决Topk问题的：
给定无序数组arr，找出：如果arr有序的话，第k小那个数是多少？
【其实就是找arr按升序排好序的数组的下标为k-1的元素】
bfprt算法是解决这个问题的最优解！
bfprt算法又称中位数的中位数算法，
它由Blum、Floyd、Pratt、Rivest、Tarjan 这几个人共同提出，
把他们名字的头字母拼接在一起（BFPRT），就称之为bfprt算法！
一、审题
示例：
arr = 5 2 7 1 4 6 3 8
k = 4
请你求：若arr排好序，则第k=4小的数，Top k=4那个数等于多少？
若arr排好序是这样的
arr = 1 2 3 4 5 6 7 8
i = 0 1 2 3 4 5 6 7
第k小，由于arr是0下标开始索引的，实际上就是k-1下标那个数
就是arr[k-1]=arr[3]=4；
这就是TopK问题
暴力解：用系统排序之后，直接获取k-1下标那个数
很简单，这个题，不就让你排序吗
系统排序算法Arrays.sort(arr)
然后arr就排序好了
直接索引arr[k-1]即可
但是这么做0分
因为复杂度为o(n*log(n))
这不是咱们的最优解
咱们要想办法优化到**o(n)**的速度
有两个方案，
（1）一个就是靠概率累加和凑运气，在快速排序过程中，提前定位k-1这个坐标。
（2）一个就是不靠概率累加和凑运气的bfprt算法，精心设计快速排序的pivot，争取以最快速度定位k-1这个坐标。
（2）中的bfprt思路完全和（1）一样，只不过pivot是精心设计的选法，
下一篇文章讲bfprt，咱们今天专门讲bfprt的基础知识：（1）
bfprt的基础重点是荷兰国旗问题partition
回忆一下，咱们的快排算法：
【1】10大排序算法之五：快排算法，快速排序【不稳定】，复杂度中，系统常用快速排序
当时呢，咱们有详细说过荷兰国旗问题
然后才利用荷兰国旗问题设计快排算法
荷兰国旗问题是想让你把数组arr的L–R范围上的数，按照pivot为分界线，把arr分成三个区间：
小于pivot的小于区
等于pivot的等于区
大于pivot的大于区
举例看
arr = 5 2 7 1 4 6 3 8
i = 0 1 2 3 4 5 6 7
不妨设pivot=5
则经过1次荷兰国旗问题partition之后
这是不是很容易理解，pivot居中了
快排算法怎么搞？
不就是接下来继续去小于区递归玩partition吗，然后去大于区递归玩partition【每一次partition要随机选择pivot】
等pivot左边已经规整有序了，pivot右边也规整有序了
整个arr不就有序了吗？
这就是快排的思想，非常简单吧！
因此，咱们要透彻理解partition的操作代码：它返回等于区的左边界和右边界
//交换
public static void swap(int[] arr, int i, int j){
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
// bfprt的基础重点是荷兰国旗问题partition
public static int[] partition(int[] arr, int L, int R, int pivot){
if (L > R) return new int[] {-1, -1};//无效
if (L == R) return new int[] {L, R};//相同L=R
//你把数组arr的L--R范围上的数，按照pivot为分界线，把arr分成三个区间：
//**小于pivot的小于区
//等于pivot的等于区
//大于pivot的大于区**
int less = L - 1;
int more = R;
int i = L;//从L开始对比
while (i < more){
//i==more停止对比
if (arr[i] == pivot) i++;//相等溜
else if (arr[i] < pivot) swap(arr, i++, ++less);//小于区推动等于区右走
else swap(arr, i, --more);//等于区推动大于区右走，i可能还需要再比
}
//i==more，还需要把pivot换到等于区
swap(arr, more, R);//此时more是等于区右边界,less是小于区右边界，+1是等于区左边界
return new int[] {less + 1, more};
}
咱可以测试一下案例：完成pivot的分区功能就行
public static void test(){
int[] arr = {5, 2, 7, 1, 4, 6, 3, 8};
int pivot = 5;
//先把pivot放到R位置
for (int i = 0; i < arr.length; i++) {
if (pivot == arr[i]) {
swap(arr, i, arr.length - 1);
break;//只需要一个
}
}
int[] range = partition(arr, 0, arr.length - 1, pivot);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] +" ");
}
System.out.println();
System.out.println("等于5区的左边界：" + range[0]);
System.out.println("等于5区的右边界：" + range[1]);
}
public static void main(String[] args) {
test();
}
结果非常OK
3 2 4 1 5 7 8 6 等于5区的左边界：4 等于5区的右边界：4
看见了没，按照pivot=5分区，小的都去左边了，大的都去右边了
笔试AC解：靠概率累加和凑运气，快速排序但只进一边
先学这个方法：（1）一个就是靠概率累加和凑运气，在快速排序过程中，提前定位k-1这个坐标。
最终你要解决TopK问题，不就是想在排序过程中搞定这个事情吗？虽然咱们不要先整体排序
咱们之前说了，快排算法
不就是接下来继续去小于区递归玩partition吗，然后去大于区递归玩partition【每一次partition要随机选择pivot】
等pivot左边已经规整有序了，pivot右边也规整有序了
整个arr不就有序了吗？
咱们简单回忆一下快排算法的代码：
//不说1版本，只复习3版本快排
public static void quickSortVersion3(int[] arr, int L, int R){
//1个数
if (L >= R) return;
//2个以上
//先选pivot，但是是随机的
//Math.random()是[0,1)的随机值
//N=R - L + 1的话
//(int) Math.random() * (R - L + 1)就是[0,N)，左闭右开的随机值
int randIndex = L + (int) Math.random() * (R - L + 1);
int pivot = arr[randIndex];
swap(arr, randIndex, R);//先将其挪到R处然后才开始玩partition
int[] equalArea = partition(arr, L, R, pivot);
//然后得到等于区左右边界,去小于区和大于区去快排去
quickSortVersion3(arr, L, equalArea[0] - 1);
quickSortVersion3(arr, equalArea[1] + 1, R);
}
//最终就完成了快排
快排算法的关键在随机选择pivot，也就是在L–R上随机选择一个位置index，然后把它跟R交换位置，去玩partition
然后得到等于区左右边界,去小于区和大于区去递归快排去
quickSortVersion3(arr, L, equalArea[0] - 1);
quickSortVersion3(arr, equalArea[1] + 1, R);
最后arr就排序好了。
最终要决TopK问题，也是在快速排序过程中搞定
这个方法称之为非bfprt算法：关键在于随机选择pivot，然后快排过程中只需要进其中一边
我们来看具体怎么做？
你不是要找arr中第k小那个数吗，也就是arr有序后，k-1位置那个数，令k-1= index
（1）如果我们在快排过程中，发现partition返回来的等于区range已经包含了index，其实就已经找到了
（2）如果index小于range[0]，就说明index在arr的左边的，还需要去arr的左边找
（3）如果index大于range[1]，就说明index在arr的右边的，还需要去arr的右边找
——但是（2）（3）一定只需要进其中1个！这就是非bfprt方法解决TOPK问题的特殊之处。
看上图，pivot=5，你要找k=4，即最终有序arr的index=k-1=3位置那个数
玩一次partition，返回range=4 4，代表等于pivot的区的下标索引为4–4，它不包含index=3
而且index
由于pivot是随机选择的，使得小于区的规模大致=大于区的规模
因此，每次partition的规模都会减半【大概率】
这就是一个概率随机问题，最后复杂度怎么算呢？下面写完代码咱们再算它。
非bfprt方法：概率累加和手撕代码
上面靠概率累加和凑运气，快速排序但只进一边的递归代码
//非bfprt：概率累加和的方法找
//你不是要找arr中第k小那个数吗，也就是arr有序后，k-1位置那个数，令k-1= **index**
//咱们要找的就是index
public static int findIndex(int[] arr, int L, int R, int index){
if (L == R) return arr[L];//index==L==R，必然包含，没啥可说的
//随机找pivot，然后玩partition
int pivotIndex = L + (int)(Math.random() * (R - L + 1));//左开右闭L--R的随机数
//将其跟R交换，方便做partition
swap(arr, pivotIndex, R);
//玩partition，拿等于区左右边界
int[] range = partition(arr, L, R, arr[R]);//pivot是arr[R]
//（1）如果我们在快排过程中，发现partition返回来的**等于区range**已经包含了index，其实就已经找到了
if (range[0] <= index && index <= range[1]) return arr[index];
//（2）如果index小于range[0]，就说明index在arr的左边的，还需要去arr的左边找
else if (index < range[0]) return findIndex(arr, L, range[0] - 1, index);
//（3）如果index大于range[1]，就说明index在arr的右边的，还需要去arr的右边找
else return findIndex(arr, range[1] + 1, R, index);
//——**但是（2）（3）一定只需要进其中1个**！这就是非bfprt方法解决TOPK问题的特殊之处。
}
主函数咋调用呢，从arr整个范围上找k
//主函数调用
public static int topKProblem(int[] arr, int k){
if (arr == null || arr.length == 0 || k < 0 || k >= arr.length) return -1;
int N = arr.length;
return findIndex(arr, 0, N - 1, k - 1);//index=k-1索引
}
public static void test2(){
int[] arr = {5, 2, 7, 1, 4, 6, 3, 8};
int k = 4;//找index=3
System.out.println(topKProblem(arr, k));
}
public static void main(String[] args) {
// test();
test2();
}
找出来确实是
4
咱们来分析一下整个递归的复杂度：findIndex(arr,L,R,index)
由于pivot是随机找的，所以呢每次大概率规模缩减一半，
你看代码中：玩了partition之后，咱们还需要进几次递归？就1次，不是（2）就是（3）
else if (index < range[0]) return findIndex(arr, L, range[0] - 1, index); //（3）如果index大于range[1]，就说明index在arr的右边的，还需要去arr的右边找 else return findIndex(arr, range[1] + 1, R, index);
快排的话，两边都需要进哦！
//然后得到等于区左右边界,去小于区和大于区去快排去
quickSortVersion3(arr, L, equalArea[0] - 1);
quickSortVersion3(arr, equalArea[1] + 1, R);
根据求递归的复杂度的master公式：
【2】递归思想求arr中最大值，递归函数先调用处理几部分，然后整理和归并信息返回
本题findIndex(arr,L,R,index)里面只调用1次递归findIndex【不是左边就是右边】，所以a=1次
每一次，由于随机性，故大概率规模是arr的N/2，所以b=2；
除了递归之外，咱们还需要partition，partition的复杂度是o(n)=o(n^d)，故d=1
根据下图对比发现：
log(b,a)=log(2,1)
这就是概率累加和推导出来的飞bfprt算法的复杂度o(n)
在排序过程中搞定，比直接排序o(n*log(n))要快吧？
下节再说
其实bfprt跟上面核心思想一模一样，只不过pivot，可不是随机找了！
//随机找pivot，然后玩partition
int pivotIndex = L + (int)(Math.random() * (R - L + 1));//左开右闭L--R的随机数
这段代码不单单是随机找，而是要精心设计pivot！
称之为中位数的中位数选择法！
下回分解！
总结
提示：重要经验：
1）非bfprt方法：快排的荷兰国旗问题partition是解决topK问题的核心所在，咱们在排序过程中找index，速度o(n)，是一个概率累加问题
2）bfprt跟上面核心思想一模一样，只不过pivot，可不是随机找了，而是精心设计的中位数的中位数作为pivot。
3）笔试求AC，可以不考虑空间复杂度，但是面试既要考虑时间复杂度最优，也要考虑空间复杂度最优。
