程序员必知的十大基础实用算法之-BFPRT(线性查找算法)
2019-07-01
加入收藏
用途
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;
#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] << " ";
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;
}
a[i] = myrand();
cout << a[i] << " ";
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;
}
