军训终于结束了呀QwQ(翘了两个星期的网络赛(逃))，在程序设计课上刷学校OJ的时候，发现世界上居然还有BFPRT这种神仙算法。什么你也没听过？没事下面我们就通过一道例题来一步一步了解神奇的BFPRT算法。

思考一下

如果给定一个n个数的数组，要你输出数组中第k大数，该怎么做？这时你也许会振臂高呼：“水题！”的确，在n不太大的时候，是有很多方法的，比如：

1.将n个数排序(比如快速排序或归并排序)，选取排序后的第k个数，时间复杂度为O(nlogn)。
2.维护一个k个元素的小根堆，存储当前遇到的最大的k个数，时间复杂度为O(nlogk)。这种方法同样适用于海量数据的处理。
3.部分的快速排序（快速选择算法），每次划分之后判断第k个数在左右哪个部分，然后递归对应的部分，平均时间复杂度为O(n)。但最坏情况下复杂度为O(n^2)。

但如果此时n=1e7时，你就不得不去考虑严格O(n)的算法了，BFPRT算法因此诞生，其通过修改快速选择算法的主元选取规则，使用中位数的中位数的作为主元，使得最坏情况下时间复杂度为O(n)。

快速选择算法源自快速排序，所以在学习神奇的快速选择之前，让我们一同复习一下快速排序算法吧！

快速排序算法

一种快速排序算法

要学习快速选择算法，就必须了解快速排序算法的原理，但不少同学过度依赖sort()函数，可能已经遗忘快速排序算法的原理。下面就让我们一同重新复习一遍快速排序算法。

快速排序和冒泡排序其实差不多，都是通过比较元素的大小，然后进行相应的交换，不过快速排序的效率要比冒泡排序高的多，因为它能运用分治的思想将一个整体一分二，二分四 ……然后每个小整体再进行比对交换，使得效率大大地提高，下面我们就来讲讲主流的快速排序算法实现吧！

假设我们现在对2 4 5 1 3这个5个数进行排序，排序过程主要分为5步：
1.先找出基准数 “2” ，方便起见，我们就取数列的第一个元素，但是在实际运用中，基准数最好还是使用rand()，并放到开头位置，防止一些毒瘤出题人……我们希望在一遍排序后，2左边的元素都比2小，2右边的元素都比2大；然后我们设立两个指针分别为 left 和 right （最左边和最右边）：

2.从右向左扫描，通过向左移动right指针，寻找比基准数小的元素。right左移过程中，我们找到比基准数小的元素“1”，我们将其赋值给left指针所指向的位置的元素：

3.从左向右扫描，通过向右移动left指针，寻找比基准数大的元素。left右移过程中，我们找到比基准数大的元素“4”，我们将其赋值给right指针所指向的位置的元素：

4.不断重复2.3两步，直到left指针与right指针重合，这样，所有的元素都被扫描了一遍。我们将基准数“2”赋值给指针重合位置的元素，这样我们就完成了一轮排序，此时，2前面的元素都比2小，2后面的元素都比2大：

5.以基准数2为分界点，对其左右两边分别重复上述过程，最终完成排序：

这样我们就完成了主流方法的快速排序，实现代码如下：

#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int i,j,k,m,n,o,p,js,jl,jk;
int a[1100000];

inline void quick_sort(int x,int y)
{
    int left=x,right=y;
    if(left>=right)return;
    int base=rand()%(right-left+1)+left;
    swap(a[left],a[base]);base=a[left];
    //步骤一

    while(left<right)
    {
        while(a[right]>base && left<right)right--;
        if(left<right)
        {
            a[left]=a[right];
            left++;
        }
        //步骤二
        while(a[left]<=base && left<right)left++;
        if(left<right)
        {
            a[right]=a[left];
            right--;
        }
        //步骤三
    }
    a[left]=base;//步骤四
    quick_sort(x,left-1);
    quick_sort(left+1,y);
    //步骤五
    return;
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    quick_sort(1,n);
    for(int i=1;i<=n;i++)printf("%d ",a[i]);
    return 0;
} 

另一种快速排序算法

其实快速排序的排序方式有两种，其时间复杂度相同，只是思想方式有所不同，下面我们就来顺便了解一下另一种快速排序算法吧。

假设我们现在还是对2 4 5 1 3这个5个数进行排序。一轮排序过程分也分为五步：
1.同样的我们要先在这个序列中随便找一个数作为基准数。方便起见，就让第一个数2作为基准数吧(具体操作中还是要随机化取基准数，并放到第一位)：

2.right指针左移，寻找第一个比基准数小的数：

3.left指针右移，寻找第一个比基准数大的数：

4.交换left和right所指向的元素：

5.重复2.3.4直到left和right相遇，交换基准数和left指针所指向的数：

这样我们就完成了一轮排序，一轮排序后基准数左边的数都比基准数小，基准数右边的数都比基准数大；

具体代码如下：

#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int left,j,k,m,n,o,p,js,jl,jk;
int a[1100000];

void quick_sort(int left,int right) 
{
    int i,j,t,temp;
    if(left>=right)return;
    temp=rand()%(right-left+1)+left;
    swap(a[left],a[temp]);
    temp=a[left];//temp中存的就是基准数

    i=left;
    j=right;
    while(i != j) 
    { //顺序很重要
        while(a[j] >= temp && i < j)j--;//要先从右边开始找 
        while(a[i] <= temp && i < j)i++;//再找左边的       
        if(i < j)swap(a[i],a[j]);//交换两个数在数组中的位置
    }
    //最终将基准数归位
    a[left]=a[i];
    a[i]=temp;
    quick_sort(left,i-1);//继续处理左边的，这里是一个递归的过程
    quick_sort(i+1,right);//继续处理右边的 ，这里是一个递归的过程
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    quick_sort(1,n);
    for(int i=1;i<=n;i++)printf("%d ",a[i]);
    return 0;
} 

快速选择算法

算法过程及实现

看完了两种快速排序，下面我们就要学习这篇BLOG的主角了——快速选择算法——BFPRT！

首先BFPRT算法为什么叫这个名字呢？这是因为在1973 年， Blum 、 Floyd 、 Pratt 、 Rivest 、 Tarjan 集体出动，合写了一篇题为 “Time bounds for selection” 的论文，给出了一种在数组中选出第 k 大元素的算法，俗称"中位数之中位数算法"。依靠一种精心设计的 pivot 选取方法，该算法从理论上保证了最坏情形下的线性时间复杂度，打败了平均线性、最坏 O(n^2) 复杂度的传统算法。而为了纪念他们五个人的突出贡献，这个算法也被命名为BFPRT算法。

快速排序算法，我们在上面已经进行讲解了，其思路是通过选择基准数，将原始数据划分为两个部分，在分别对两部分数据按同样的方法分治递归，通过不断的递归将大的问题划分为两个小的子问题，达到快速的目的，算法的平均时间复杂度为O(nlogn), 这里的基准数的选择很关键，如果选择的是最大值或是最小值，那么划分的连个子问题将会严重不平衡，算法的最坏复杂度将会达到O(nn)。关于基准数的选择，在算法导论中有详细的讨论，主要有随机选择，三元素取中值，五划分中项的中项法。

而五划分中项的中项法就是BFPRT算法，并具有以下性质：

1.此算法可以保证每个递归的子问题的大小最多是原问题的的大约70%

2.对于整个选择算法，基准数可以足够算法算出，保证O(n)的运行时间

这里的算法复杂度的分析，将放在算法实现之后单独讲解。

下面给出主要实现步骤：

step1：将n个元素每5个一组，分成 n/5(下界)组，最后的一个组若不足5个，直接舍去。

step2：取出每一组的中位数，最后一个组的不用计算中位数，任意排序方法，这里的数据比较少只有5个，可以用简单的冒泡排序或是插入排序。

step3 :  将各组的中位数与数组开头的数据在组的顺序依次交换，这样各个组的中位数都排在了数据的左边。递归的调用中位数选择算法查找上一步中所有组的中位数的中位数，设为x，偶数个中位数的情况下设定为选取中间小的一个。

step4:   按照x划分,大于或者等于x的在右边,小于x的在左边。

step5：step4中划分后数据后返回一个下标i，i左边的元素均是小于x，i右边的元素包括i都是大于或是等于x的:

1.若i==k，返回x；

2.若i<k，在小于x的元素中递归查找第i小的元素；

3.若i>k，在大于等于x的元素中递归查找第i-k小的元素。

下面我们就来一步一步实现BFPRT算法吧！

首先，我们先在BFPRT函数里，列举要做的事：

int BFPRT(int left,int right,int k)
//求第k小，返回其位置的下标
{
    int pivot_index=GetPivotIndex(left,right);//得到中位数的中位数下标
    int divide_index = Partition(left,right,pivot_index);//进行划分，返回划分边界
    int num=divide_index-left+1;
    if (num == k)return divide_index;
    else if (num>k)return BFPRT(left,divide_index-1,k);
    else return BFPRT(divide_index+1,right,k-num);
}

接下来我们一步一步来实现，首先是要得到中位数的中位数下标：

int GetPivotIndex(int left,int right)
 //返回中位数的中位数下标
{
    if (right-left<5)return(InsertSort(left, right));

    int sub_right=left-1;
    for (int i=left;i+4<=right;i+=5)
    {
        int index=InsertSort(i,i+4);  //找到五个元素的中位数的下标
        swap(a[++sub_right], a[index]);   //依次放在左侧
    }

    return BFPRT(left,sub_right,((sub_right-left+1)/2)+1);
}

在其中我们要用到选择排序求出5个或者更小的几个数中的中位数的下标：

int ChooseSort(int left,int right)
//选择排序，返回中位数下标
{
    int temp;
    for(int i=left;i<right;i++)
    for(int j=i+1;j<=right;j++)
    {
        if(a[i]>a[j])swap(a[i],a[j]);
    }
    return(((right-left)/2)+left);
}

最后我们还需要划分，将小于基准数的数放在基准数左边，大于基准数的数放在基准数右边，并且返回分界线下标：

int Partition(int left,int right,int pivot_index)
//利用中位数的中位数的下标进行划分，返回分界线下标
{
    swap(a[pivot_index],a[right]);  //把基准放置于末尾

    int divide_index=left;  //跟踪划分的分界线
    for (int i=left;i<right;i++)
    {
        if (a[i]<a[right])
            swap(a[divide_index++],a[i]);  //比基准小的都放在左侧
    }

    swap(a[divide_index], a[right]);  //最后把基准换回来
    return divide_index;
}

到这里，程序的主体就完成了，完整模板将在下面的经典例题中给出。

算法复杂度分析

时间复杂度还是很难分析的，但感谢一位大佬的证明思路，下面就让我们一起看看吧。

BFPRT算法在最坏情况下的时间复杂度是O(n)，下面予以证明。令T(n)为所求的时间复杂度，则有：
T(n)≤T(n/5)+T(7n/10)+cn

其中：

1.T(n/5)来自GetPivotIndex()，n个元素，5个一组，共有⌊n/5⌋个中位数；
2.T(7n/10)来自BFPRT()，在⌊n/5⌋个中位数中，主元x大于其中 1/2⋅n/5=n/10的中位数，而每个中位数在其本来的5个数的小组中又大于或等于其中的3个数，所以主元x至少大于所有数中的n/10⋅3=3n/10个。即划分之后，任意一边的长度至少为3/10，在最坏情况下，每次选择都选到了7/10的那一部分。
3.c⋅n来自其它操作，比如InsertSort()，以及GetPivotIndex()和Partition()里所需的一些额外操作。

设T(n)=t⋅n，其中t为未知，它可以是一个正常数，也可以是一个关于n的函数，代入上式：

t⋅n≤t⋅n/5+7t⋅n/10+c⋅n(两边消去n)
t≤t/5+7t/10+c(再化简)
t≤10c(c为一个正常数)

其中c为一个正常数，故t也是一个正常数，即T(n)≤10c⋅n，因此T(n)=O(n)，至此证明结束。

接下来的更有意思的话题就是BFPRT算法为何选5作为分组基准，为何不是2,3,7,9呢？
首先排除偶数，对于偶数我们很难取舍其中位数，而奇数很容易。
再者对于3而言，会有T(n)≤T(n/3)+T(2n/3)+c⋅n，它本身还是操作了n个元素，与以5为基准的9n/10相比，其复杂度并没有减少。
对于，7，9，…而言，对于上式中的10c，其整体都会增加，所以与5相比，5更适合。

经典例题

【matrix 23】寻找第K大数

Description
给定一个n个数的数组，输出数组中第k大数。

Input
第一行包含两个数n < 10000000, k，第二行为n个整数。

Output
输出第k大数。

Sample Input
5 3
3 2 1 4 5
Sample Output
3
Note
不使用O(n)算法可能会TL。

模板题，直接贴上模板即可。

#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring> 
#include<algorithm>
using namespace std;

int n,m,k;
int a[1100000];

int ChooseSort(int left,int right);//选择排序，返回中位数下标
int BFPRT(int left,int right,int k);//求第k小，返回其位置的下标
int GetPivotIndex(int left,int right);//返回中位数的中位数下标
int Partition(int left,int right,int pivot_index);//利用中位数的中位数的下标进行划分，返回分界线下标

int ChooseSort(int left,int right)
//选择排序，返回中位数下标
{
    int temp;
    for(int i=left;i<right;i++)
    for(int j=i+1;j<=right;j++)
    {
        if(a[i]>a[j])swap(a[i],a[j]);
    }
    return(((right-left)/2)+left);
}

int GetPivotIndex(int left,int right)
 //返回中位数的中位数下标
{
    if (right-left<5)return(ChooseSort(left, right));

    int sub_right=left-1;
    for (int i=left;i+4<=right;i+=5)
    {
        int index=ChooseSort(i,i+4);  //找到五个元素的中位数的下标
        swap(a[++sub_right], a[index]);   //依次放在左侧
    }

    return BFPRT(left,sub_right,((sub_right-left+1)/2)+1);
}

int Partition(int left,int right,int pivot_index)
//利用中位数的中位数的下标进行划分，返回分界线下标
{
    swap(a[pivot_index],a[right]);  //把基准放置于末尾

    int divide_index=left;  //跟踪划分的分界线
    for (int i=left;i<right;i++)
    {
        if (a[i]<a[right])
            swap(a[divide_index++],a[i]);  //比基准小的都放在左侧
    }

    swap(a[divide_index], a[right]);  //最后把基准换回来
    return divide_index;
}

int BFPRT(int left,int right,int k)
//求第k小，返回其位置的下标
{
    int pivot_index=GetPivotIndex(left,right);//得到中位数的中位数下标
    int divide_index = Partition(left,right,pivot_index);//进行划分，返回划分边界
    int num=divide_index-left+1;
    if (num == k)return divide_index;
    else if (num>k)return BFPRT(left,divide_index-1,k);
    else return BFPRT(divide_index+1,right,k-num);
}

int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]); 
    printf("%d",a[BFPRT(1,n,n-k+1)]);//第k大即第n-k+1小的数
    return 0;
}

P.S. 这个OJ有毒，评测了好多次才通过……

结语

通过这篇BLOG，我们一同复习了两种快速排序算法，还实现了圣经般神奇的BFPRT算法，你一定有所收获吧。最后希望你喜欢这篇BLOG！