select.cpp

选择问题

#include<iostream.h>
#include<algorithm>
using namespace std;
int SelectNmuber(int A[],int n,int k);
void merge(int A[],int p,int q,int r,int m){
	int *bp=new int[m];   //分配缓冲区，存放被排序的元素
	int i,j,k;
	i=p;j=q+1;k=0;
	while(i<=q && j<=r){   //逐一判断两子数组的元素
		if(A[i]<=A[j])   //按两种情况，把小的元素复制到缓冲区
			bp[k++]=A[i++];
		else bp[k++]=A[j++];}
	if(i==q+1){   //按两种情况，处理其余元素
		for(;j<=r;j++)
			bp[k++]=A[j];}   //把A[j]～A[r]复制到缓冲区
	else {
		for(;i<=q;i++)
			bp[k++]=A[i];}   //把A[i]～A[q]复制到缓冲区
	k=0;
	for(i=p;i<=r;i++)   //最后，把数组bp的内容复制到A[p]～A[r]
		A[i]=bp[k++];
	delete bp;}
void merge_sort(int A[],int n){
	int i,s,t=1;
	while(t<n){
		s=t;t=2*s;i=0;
		while(i+t<n){
			merge(A,i,i+s-1,i+t-1,t);
			i=i+t;}
		if(i+s<n)
			merge(A,i,i+s-1,n-1,n-i);}}
void mid(int A[],int i,int 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 SelectNmuber(int A[],int n,int k){
	int i,j,s,t,m,*p,*q,*r;
	if(n<=27){   //元素个数小于阀值，直接排序
		merge_sort(A,n);
		return A[k-1];}   //返回第K小的元素
	p=new int[3*n/4];
	q=new int[3*n/4];
	r=new int[3*n/4];
	cout<<"the mid number is: ";
	for(i=0;i<n/5;i++){   //把每组5个元素的中值元素依次存于p
		mid(A,i,p);
		cout<<p[i]<<"  ";}
	cout<<endl;
	m=SelectNmuber(p,i,i/2+i%2);   //递归调用，取得中值元素的中值元素于m
	cout<<"the mid number of mid number is: "<<m<<endl;
	i=j=s=0;
	for(t=0;t<n;t++){   //根据m，把原数组划分为p,q,r三部分
		if(A[t]<m)
			p[i++]=A[t];
		else if(A[t]==m)
			q[j++]=A[t];
		else r[s++]=A[t];}
		int tempi=i,tempj=j,temps=s;
		cout<<"the number smaller than m is: ";
		for(i=0;i<tempi;i++)
			cout<<p[i]<<"  ";
			cout<<endl;
		cout<<"the number equal to m is: ";
		for(j=0;j<tempj;j++)
			cout<<q[j]<<"  ";
			cout<<endl;
		cout<<"the number larger than m is: ";
		for(s=0;s<temps;s++)
			cout<<r[s]<<"  ";
			cout<<endl;
		i=tempi;	j=tempj;	s=temps;
		if(i>=k)   //第K小元素在数组p中，继续在p中寻找
			return SelectNmuber(p,i,k);
		else if(i+j>=k)   //m就是第K小元素
			return m;
		else return SelectNmuber(r,s,k-i-j);}   //第K小元素在数组r中，继续在r中寻找
void main(){
	int *array,size,number,a;
	cout<<"please input the size of array: ";
	cin>>size;
	array=new int[size+1];
	cout<<"please input the array:"<<endl;
	for(int i=0;i<size;i++)
		cin>>array[i];
	cout<<"please input the 'x' of NO.x small number : ";
	cin>>number;
	if(number>size)
		cout<<"error: the number must no lagrer than size."<<endl;
	else{
		cout<<"********************** the course of first recursion is: **********************"<<endl;
		a=SelectNmuber(array,size,number);
		cout<<"*******************************************************************************"<<endl;
		cout<<"the NO."<<number<<" small number is: ";
		cout<<a<<endl;}}