BFPRT算法求第k大数

╰+攻爆jí腚メ 2022-09-17 12:20 140阅读 0赞

偶然间看到的东西，简单的看了看，不明觉厉……查了些资料，留待以后学习。

[BFPRT算法\_小彰\_百度空间][BFPRT]

[十四、第三章再续：快速选择SELECT算法的深入分析与实现 - 结构之法 算法之道 - 博客频道 - CSDN.NET][SELECT_ - _ _ - _ - CSDN.NET]

[找最小的K个数 - Stay hungry, Stay foolish - 博客频道 - CSDN.NET][K_ - Stay hungry_ Stay foolish - _ - CSDN.NET]

[线性查找算法，BFPRT 算法\_const void \* const pHeart=new(myheart) you("love")；\_百度空间][BFPRT _const void _ const pHeart_new_myheart_ you_love]

以下一段代码转自：http://yoyo.is-programmer.com/posts/8207.html

#include <iostream>
    #include <algorithm>
    using namespace std;
    
    /***************************************
    * 选择第k小元素算法
    *
    * 输入：元素数组A[]，元素个数n，求的k
    * 输出：第k小元素
    ***************************************/
    template<class Type>
    Type select (Type A[], int n, int k)
    {
    	int i,j,s,t;
    	Type m,*p,*q,*r;
    	if (n<38)
    	{ //     如果元素个数小于38：则直接排序
    		sort(A,A+n);
    		return A[k-1];
    	}
    	p = new Type[3*n/4];
    	q = new Type[3*n/4];
    	r = new Type[3*n/4];
    	for ( i=0; i<n/5; i++)
    	{  //        五个一组，把每组的中值元素存放进数组p
    		mid(A,i,p);
    	}
    	m = select(p, i, i/2+i%2);      //    递归调用，取得中值元素存入m
    	i = j = s = 0;
    	for( t=0; t<n; i++)
    	{    //  按<m、=m、>m把数组分成三组
    		if(A[t]<m)
    			p[i++] = A[t];
    		else
    		{
    			if (A[t]==m)
    				q[j++] = A[t];
    			else
    				r[s++] = A[t];
    		}
    	}
    	if (i>k)
    	{  //      若k<i，则该元素就在数组p中，进入p继续查找
    		return select(p,i,k);
    	}
    	else
    	{
    		if(i+j>=k)
    		{ //   若i<k<i+j，则该元素在q数组中，即值为m
    			return m;
    		}
    		else
    		{ //若k>i+j，则该元素在r数组中，进入r继续寻找
    			return select(r,s,k-i-j);
    		}
    	}
    }
    
    /***************************************
    * 计算中值元素
    *
    * 输入：元素数组A[]，组号i
    * 输出：存放中值元素的数组p[]
    ***************************************/
    template <class Type>
    void mid (Type A[], int i, Type p[])
    {
    	int k = 5*i;
    	if (A[k]>A[k+2])
    		swap(A[k], A[k+2]);
    	if (A[k+1]>A[k+3])
    		swap(A[k+1], A[k+3]);
    	if (A[k]>A[k+1])
    		swap(A[k],A[k+1]);
    	if (A[k+2]>A[k+3])
    		swap(A[k+2],A[k+3]);
    	if (A[k+1]>A[k+2])
    		swap(A[k+1],A[k+2]);
    	if (A[k+4]>A[k+2])
    		p[i] = A[k+2];
    	else
    	{
    		if (A[k+4]>A[k+1])
    			p[i] = A[k+4];
    		else
    			p[i] = A[k+1];
    	}
    }
    
    int main ()
    {
            int n,m;
    
            cout<<"请输入数组元素个数：";
            cin>>n;
    
            cout<<"请输入要求的k：";
            cin>>m;
    
            int *A = new int[n];
            int i;
    
            cout<<"请输入数组元素："<<endl;
            for(i=0;i<n;i++){
                    cin>>A[i];
            }
    
            cout<<"第"<<m<<"大元素是：";
            cout<<select(A,n,n-m+1)<<endl;    // 输出第(n-m+1)小元素<=>第m大元素
    
            return 0;
    }

[BFPRT]: http://hi.baidu.com/hins_pan/item/8a3e9f97358f17bf83d29540
[SELECT_ - _ _ - _ - CSDN.NET]: http://blog.csdn.net/v_JULY_v/article/details/6431001
[K_ - Stay hungry_ Stay foolish - _ - CSDN.NET]: http://blog.csdn.net/huagong_adu/article/details/6901924
[BFPRT _const void _ const pHeart_new_myheart_ you_love]: http://hi.baidu.com/hj11yc/item/9b9e11d941b4a1f6cb0c39db