最近在学习算法，平常没有写博客的习惯，慢慢发现，有些东西写了自己的印象才会更加深刻，每次看着那些牛人写的博客，总是心生感叹，琢磨着自己也写几篇博客。
————写在自己的第一篇CSDN博客前言
原创文章：转载请注明出处
一 算法由来
BFPRT 算法：1973 年， Blum 、 Floyd 、 Pratt 、 Rivest 、 Tarjan 集体出动，合写了一篇题为 “Time bounds for selection” 的论文，给出了一种在数组中选出第 k 大元素的算法，俗称"中位数之中位数算法"。依靠一种精心设计的 pivot 选取方法，该算法从理论上保证了最坏情形下的线性时间复杂度，打败了平均线性、最坏 O(n^2) 复杂度的传统算法。一群大牛把递归算法的复杂度分析玩弄于股掌之间，构造出了一个当之无愧的来自圣经的算法。
——-摘引自大神的博客
二 算法主要思想
快速排序算法，相信很多人都明白，通过选择枢纽元，将原始数据划分为两个部分，在分别对两部分数据按同样的方法分治递归，通过不断的递归将大的问题划分为两个小的子问题，达到快速的目的，算法的平均时间复杂度为O(n*logn), 这里的枢纽元的选择很关键，如果选择的是最大值或是最小值，那么划分的连个子问题将会严重不平衡，算法的最坏复杂度将会达到O(n*n)。关于枢纽元的选择，在算法导论或是Mark Allen Weiss的数据结构中都有详细的讨论，主要有随机选择，三元素取中值，五划分中项的中项法。
五划分中项的中项法就是BFPRT算法。Mark Allen Weiss的数据结构中P282中介绍了此算法，并给出了相关证明：
1.此算法可以保证每个递归的子问题的大小最多是原问题的的大约70%
2.对于整个选择算法，枢纽元可以足够算法算出，保证O(n)的运行时间
这里的算法复杂度的分析，可以参看相关书籍和本文最后列出的大神博客，本文不做叙述。
这里有一个福州大学的教学视频，?id=82，感谢这个视频的创作者，关于算法的讲解用视频的方式最能够让人理解了。
下面是算法主要步骤：
其中有些细节的处理，主要是边界问题还是比较关键，后面会给出这些问题。
数据有n个，取出最小的k个数字
终止条件：n=1时，返回的即是i小元素。
算法步骤：
step1：将n个元素每5个一组，分成n/5(上界)组，最后的一个组的元素个数为n%5，有效的组数为n/5。
step2：取出每一组的中位数，最后一个组的不用计算中位数，任意排序方法，这里的数据比较少只有5个，
可以用简单的冒泡排序或是插入排序。
setp3 : 将各组的中位数与数组开头的数据在组的顺序依次交换，这样各个组的中位数都排在了数据的左边。
递归的调用中位数选择算法查找上一步中所有组的中位数的中位数，设为x，偶数个中位数的情况下设定为选取中间小的一个。
setp4: 按照x划分,大于或者等于x的在右边,小于x的在左边，关于setp4数据的划分，中位数放在左边或是右边会有些影响。
后面的代码调试将会看到。
step5：setp4中划分后数据后返回一个下表i，i左边的元素均是小于x，i右边的元素包括i都是大于或是等于x的。
若i==k，返回x；
若i<k，在小于x的元素中递归查找第i小的元素；
若i>k，在大于等于x的元素中递归查找第i-k小的元素。
三 网上的算法代码剖析
我在网上找了一下，发现很多介绍BFPRT算法，要么只介绍了算法思想，没有给出代码实现，给出代码实现的基本上是下面的代码
代码来源
#include<iostream>#include<stdlib.h>#include<time.h>using namespace std;#define MAX_VALUE 10#define random() rand()%MAX_VALUE#define N 10int a[N]; class Find {public:void bubble(int first, int end) //冒泡排序{for (int flag = first; flag < end; flag++){for (int i = end; i > flag; i–){if (a[i] < a[i – 1]){int t = a[i];a[i] = a[i – 1];a[i – 1] = t;}}}}int partition(int p, int r, int x) //数组a中从a[p]到a[r]的元素按照x划分,大于x的在左边,小于x的在右边{int i, j;for (i = p, j = r; i < j; i++){if (a[i] > x){while (i < j && a[j] > x) {j–;}if (i != j) {int t = a[i];a[i] = a[j];a[j] = t;j–;}}}return i – 1;}int select(int p, int r, int k) //寻找中位数{int i;if (r – p < 5){bubble(p, r);return a[p + k – 1];}for (i = 0; i < (r – p – 4) / 5; i++){int s = p + 5 * i, t = s + 4;bubble(s, t);int temp = a[p + i];a[p + i] = a[s + 2];a[s + 2] = temp;}int x = select(p, p + (r – p – 4) / 5, (r – p + 6) / 10);i = partition(p, r, x);int j = i – p + 1;if (k <= j) {return select(p, i, k);}else {return select(i + 1, r, k – j);}}};int main(){// clock_t start,end;// double elapsed;// srand((int)time(NULL));for (int k = 0; k < N; k++){a[k] = random();cout << a[k] << " ";}// start=clock();Find f;int n = 4;cout << "The No." << n << " is :" << f.select(0, N – 1, n) << endl;// end=clock();// elapsed=((double)(end-start));//CLOCKS_PER_SEC;// cout<<"Time: "<<elapsed<<endl;cout << "最小的" << n << "个元素为：" << endl;for (int k = 0; k < n; k++){cout << a[k] << " ";}return 0;}
这份代码的首创者写的还是不错的，框架很清楚，代码还是有以下问题：
1"intpartition(intp,intr,intx)//数组a中从a[p]到a[r]的元素按照x划分,大于x的在左边,小于x的在右边"
代码的注释有问题，误导读者，实际的代码编写的应该是大于x的在右边,小于或是等于x的在左边，
那些博客贴上去的代码，没有更改这个注释，大致是他们没有亲自测试过这些代码就从其他地方弄过来了。
在向山靠近一点，才发现这座山，好象一位诗人遥望远方，
