用途

BFPRT算法解决的问题十分经典，即从某n个元素的序列中选出第k大（第k小）的元素，通过巧妙的分析，BFPRT可以保证在最坏情况下仍为线性时间复杂度。该算法的思想与快速排序思想相似，当然，为使得算法在最坏情况下，依然能达到o(n)的时间复杂度，五位算法作者做了精妙的处理。

原理

在原表长n的基础上增加一个元素n+1，将K值送入此元素的关键字项中，这样在循环回路上只要进行一次比较，我们把第n+1个记录称为“监视哨”。这样当n很大时几乎可以节省一半时间。

在顺序查找中，在找到第i个记录时，给定值K和记录中的关键字进行了i次比较。

由于平均查找长度与表长度n成线性关系，因此当n较大时，顺序查找的效率较低。但顺序查找算法比较简单，且对顺序表的存储结构没有限制，既可以用向量作存储结构也可以用链表作存储结构。

步骤

1、将n个元素每5个一组，分成n/5(上界)组。

2、取出每一组的中位数，任意排序方法，比如插入排序。

3、递归的调用selection算法查找上一步中所有中位数的中位数，设为x，偶数个中位数的情况下设定为选取中间小的一个。

4、用x来分割数组，设小于等于x的个数为k，大于x的个数即为n-k。

5、若i==k，返回x；若i<k，在小于x的元素中递归查找第i小的元素；若i>k，在大于x的元素中递归查找第i-k小的元素。

终止条件：n=1时，返回的即是i小元素。

代码

#include <iostream>
#include <cstdlib>
using namespace std;
#define SIZE 20
#define myrand() rand() % SIZE
void bubble(int a[], int start, int end){
 for(int i = 0; i <= end-start; i++){
 for(int j = start; j < end - i; j++){
 if(a[j] > a[j+1]){
 int tmp = a[j];
 a[j] = a[j+1];
 a[j+1] = tmp;
 }
 }
 }
}
int partition(int a[], int start, int end, int x){
 for(;start < end; start++){
 if(a[start] > x){
 while(start < end && a[end] > x)
 end--;
 if(start != end){
 int tmp = a[end];
 a[end] = a[start];
 a[start] = tmp;
 }else
 break; //这里一定要加这条语句，否则外部循环start会在+1
 }
 }
 return start - 1;
}
int select(int a[], int start, int end, int k){
 int i, s, t;
 if(end - start < 5){
 bubble(a,start,end);
 return a[start+k-1];
 }
 for(i = 0; i < (end-start+1)/5; i++){
 s = start + 5*i;
 t = s + 4;
 bubble(a,s,t);
 int tmp = a[start+i];
 a[start+i] = a[s+2];
 a[s+2] = tmp;
 }
 if((end-start+1) % 5 != 0){
 s = start + 5*i;
 bubble(a,s,end);
 int tmp = a[start+i];
 a[start+i] = a[(s+end)/2];
 a[(s+end)/2] = tmp;
 i++;
 }
 i--;
 int x = select(a,start, start+i, (i+1)/2);
 i = partition(a,start, end, x);
 int j = i - start + 1;
 //这里之所以没有加入j == k的判断是因为在partiton时无法将x排在正确的位置使得左边都小于x而右边都大于x只能保证一边>,另一边<=;
 if(j >= k)
 return select(a, start, i, k);
 else
 return select(a, i+1, end, k-j);
}
int main(){
 clock_t start, end;
 srand((int)time(NULL));
 int a[SIZE];
 int n = 5;
 
 for(int i = 0; i < SIZE; i++){
 a[i] = myrand();
 cout << a[i] << "\t";
 if((i+1)%5 == 0)
 cout << endl;
 }
 start = clock();
 cout << "the no " << n << " is: " << select(a, 0, SIZE-1, n) << endl;
 end = clock();
 cout << "Time: " << (double)(end - start) << endl;
 return 0;
}

欢迎大家来到IT世界,在知识的湖畔探索吧!