用途
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;
