线性时间选择算法.cpp

递归和分治法解一系列经典算法

//线性时间选择算法

#include <iostream.h>
#include <stdlib.h>
template <class Type>

void Swap(Type &x, Type &y)
{
    Type temp = x;
    x = y;
    y = temp;
} 

template <class Type>
Type Partition(Type a[], int p, int r)
{
    int i=p, j=r+1;
	Type x=a[p];
    while(true)
    {
        while(a[++i]<x && i<r);
        while(a[--j]>x);
        if(i>=j) break;
		Swap(a[i], a[j]);
	}
	a[p]=a[j];
	a[j]=x;
    return j;
}

template<class Type>
RandomizedPartition(Type a[], int p, int r)
{
	int i=rand()%(r-p+1)+p;
	Swap(a[i],a[p]);
	return Partition(a,p,r);
}

template<class Type>
Type RandomizedSelect(Type a[], int p, int r, int k)
{
	if (p==r) return a[p];
	int i=RandomizedPartition(a, p, r), j=i-p+1;
	if (k<=j) return RandomizedSelect(a, p, i, k);
	return RandomizedSelect(a, i+1, r, k-j);
}

void main()
{
    int n,i, k=0, *a;
	cout<<"请输入整数的个数n：";
	cin>>n;
	a=new int[n];
	cout<<"请输入"<<n<<"个整数：";
    for(i=0; i<n; i++)
	{
		cin>>a[i];	
	}
	
	while(k<1||k>n){
        cout<<"要找第几个小的数[1，"<<n<<"]：";
		cin>>k;
	}
	cout<<"第 "<<k<<" 个小的数是：";
    cout<<RandomizedSelect(a, 0, n-1, k)<<endl;
}