BFPRT算法（求第K小的数字）

BFPRT算法：

1.介绍：

BFPRT算法又叫中位数的中位数算法，主要用于在无序数组中寻找第K大或第K小的数，它的最坏时间复杂度为O(n)，它是由Blum，Floyd，Pratt，Rivest，Tarjan提出，它的思想是修改快速选择算法（快排）的主元选取方法，提高在最坏情况下的时间复杂度。

2.具体方法：

BFPRT算法主要由两部分组成：快排和基准选取函数。基准选取函数就是中位数的中位数算法的实现，具体来说--就是讲快排的基准选取策略进行了优化，改为每次尽可能的选择中位数作为基准。

所以说算法的核心就是通过基准选取函数找一个合理的划分值，然后就是快排的Partition过程，判断等于区域（利用区域的下标进行判断）是否命中k，否则向两边其中一边递归。

实现过程：

1.将给定的数组‘arr[N]’划分为多个小组，每5个一组，小于5个的单独成组，只是在逻辑上对数组进行了分组，时间复杂度为O(N)

2.每个组进行组内排序，对5个数的排序时间是O(1)，只保证组内有序，共有N/5个组，时间复杂度：O(1)*N/5=O(N).

3.得到每个组的“上中位数”，在组成新的数组newarr[]（未必有序），长度是N/5。

[上中位数]：

对于奇数个数，就是中位数，比如 1 2 3 4 5，中位数：3

对于偶数个数，为前一个数，比如 1 2 3 4 ，中位数为：2

4.然后求得newarr[]的中位数，即中位数的中位数mm，作为划分值。

5.Partition过程：时间复杂度：O(N).

6.判断快排后左右指针重合的位置i+1是否等于k,大于则向右递归，小于则向左递归。

看完算法的过程，我们知道主要有这些函数：1.求中位数，2.Partition函数，3.插入排序函数（被求中位数函数调用），4.求key（即中位数的中位数）。

#include <iostream>

#include <vector>

using namespace std;

int  GetMedian(vector<int>a,int begin, int end);

int  medianOfMedians(vector<int>a, int begin, int end);

void InsertSort(vector<int>&a,int begin, int end);

int  select(vector<int>&a, int begin, int end, int K);

int  Get_MinKnum_By_BFPRT(vector<int>&a,int K);

vector<int> Partition(vector<int>&a, int l,int r, int pKey);

int main()

{

	printf("初始数组a中的元素：");

	for(int i = 0; i<a.size();++i)

		cout<<a[i]<<" ";

	cout<<"\n\n";

	printf(" Get_MinKnum_By_BFPRT 获得的第5大的数是：%d\n\n",Get_MinKnum_By_BFPRT(a,5));

	printf("用于检验：数组a排序后的元素：");

	InsertSort(a,0,a.size()-1);

	for(int i = 0; i<a.size();++i)

		cout<<a[i]<<" ";

	cout<<"\n\n";

	return 0;

}

//插入排序(为了求取中位数)

void InsertSort(vector<int>&a,int begin,int end)

{

	if(begin == end)	return;

	for (int i = begin+1; i != end+1; ++i)

	{

		for (int j = i - 1; j >= begin ; j--)

		{

			if(a[j+1] < a[j])

				swap(a[j],a[j+1]);

			else

				break;

		}

	}

}

//获取中位数

int GetMedian(vector<int>a,int begin, int end)

{

	InsertSort(a,begin,end);

	int sum = begin+end;

	int mid = (sum/2) + (sum%2);

	return a[mid];

}

//Partition过程

vector<int> Partition(vector<int>&a, int l,int r, int pKey)

{

	int less = l-1;

	int more = r+1;

	int pos  = l;

	while(pos < more)

	{

		if(a[pos] < pKey){

			swap(a[++less],a[pos++]);

		}else if (a[pos] > pKey){

			swap(a[--more],a[pos]);

		}else{

			pos++;

		}

	}

	std::vector<int> range;

	range.push_back(less+1);

	range.push_back(more-1);

	return range;

}

//求取划分值pKey,中位数数组的中位数

int medianOfMedians(vector<int>a, int begin, int end)

{

	int num = end-begin+1;

	int offset = num % 5 == 0 ? 0 : 1;	//用于不足5个元素自成一组

	std::vector<int> newarr(num/5+offset);

	for (int i = 0; i < newarr.size(); ++i)

	{

		int beginI = begin + i*5;

		int endI = beginI + 4;

		//GetMedian()是获取每组的中位数，之后存到新数组中

		newarr[i] = GetMedian(a,beginI,min(end,endI));	//取min值是因为要处理不足5个一组的情况

	}

	return select(newarr,0,newarr.size()-1,newarr.size()/2);	//获取newarr[]的中位数

	//递归的调用自己求上中位数

}

//select函数：给定一个数组和范围，求位于第k位置上的数

int select(vector<int>&a, int begin, int end, int K)

{

	if(begin == end)

		return a[begin];

	int pKey = medianOfMedians(a,begin,end);

	vector<int> range = Partition(a,begin,end,pKey);

	if (K >= range[0] && K <= range[1]){

		return a[K];

	}

	else if (K < range[0]) {

		return select(a, begin, range[0]-1, K);

	}

	else {

		return select(a, range[1] + 1, end, K);

	}

}

int Get_MinKnum_By_BFPRT(vector<int>&a,int K)

{

	return select(a,0,a.size()-1,K-1);

}

读到这里大家肯定还是一知半解，很多地方还是云里雾里，例如为甚吗一定要将数组划分为N/5，这个我也不是很明白，有兴趣的可以看看BFPRT算法原理,讲的更加深入.

巴特西

BFPRT算法（求第K小的数字）

BFPRT算法：

1.介绍：

2.具体方法：

最新文章

热门文章