【蒟蒻算法】从快速排序到快速选择-BFPRT

军训终于结束了呀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 (最左边和最右边):1.png

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

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

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

4.png

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

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

#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作为基准数吧(具体操作中还是要随机化取基准数,并放到第一位):
1.png
2.right指针左移,寻找第一个比基准数小的数:

1_2.png

3.left指针右移,寻找第一个比基准数大的数:
1_3.png

4.交换left和right所指向的元素:
1_4.png

5.重复2.3.4直到left和right相遇,交换基准数和left指针所指向的数:
1_5.png
1_6.png

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

具体代码如下:

#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有毒,评测了好多次才通过……
AC.png

结语

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

Last modification:September 29th, 2019 at 06:48 pm
If you think my article is useful to you, please feel free to appreciate

7 comments

  1. cckk

    看到大佬更新了果断跑过来ORZ。递归有点绕,暂时还没有康明白代码,明天再康康。请教个问题,大佬如何比较BFPRT与直接裸快排+随机法的优劣呢。因为裸快排虽然上限比较高,但实践中BFPRT可以比纯快排+随机快多少呢qwq。希望大佬做实验康康qwq。

    1. jvruo
      @cckk

      好的感谢您的建议,首先快排是平均O(nlogn),但是我们只要求解第k大的数,所以有一些数在分区以后就没必要继续排序了,故BFPRT算法是严格O(n)的。至于实验会在近日补上QwQ,感谢您的建议!!

      1. cckk
        @jvruo

        哇,大佬回复我了,好感动!
        当然当然,不可能完整的快排啦,我说的是选择区间的快排。
        int quick_sort(int left, int right)
        {
        int i, j, t, temp;
        if (left >= right)return a[k];
        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; int ans = 0; if(k<=i) ans = quick_sort(left, i - 1);//继续处理左边的,这里是一个递归的过程 else ans = quick_sort(i + 1, right);//继续处理右边的 ,这里是一个递归的过程 return ans;

        }
        这是我拿您的第二版本的quicksort改的,加了ans,if和返回值就没其他改动了。
        理论上,一般情况是O(2n)复杂度的,但上下限很夸张,最坏O(n^2),最好O(1)(随机万岁!)
        您看我算法多强:震惊,k大查询最好复杂度竟然是O(1)!Σ(っ °Д °;)っ

        1. jvruo
          @cckk

          哈哈哈O(1)你个鬼,你第一遍将数分为左右两块就O(n)了……

          1. cckk
            @jvruo

            我判断加前面就o1了#滑稽

        2. cckk
          @cckk

          但是就是不知道实战如何,期待大佬的回复,嘤嘤嘤!

          1. jvruo
            @cckk

            近日实战可能很血腥(滑稽

Leave a Comment