cpp1.cpp

此代码查找序列中指定第几大小的程序

#include<iostream.h>
#include<string.h>

int process(int start,int tail,int b[]);
int find(int start,int tail,int k,int b[]);

void main()/*数列的第一个数和最后一个数不能相等，除非所有数都相等*/
{
	int s;
	int a,*b;
	cout<<"输入数据的个数："<<endl;
	cin>>s;
	cout<<"输入数据："<<endl;
	b=new int[s];
	for(int i=0;i<s;i++)
		cin>>b[i];
	cout<<"输入查找第几小的数："<<endl;
	cin>>a;
	cout<<"第"<<a<<"小的数为：";
	cout<<find(0,s-1,a,b)<<endl;
	cout<<"目前数列顺序为："<<endl;
	for(i=0;i<s;i++)
		cout<<b[i]<<" ";
	cout<<endl;
}

int process(int start,int tail,int b[])/*将数列分成以n/2为界线前半部分和后半部分，前半部分所有的数都小于后半部分任意一数*/
{
	int i,j,temp,x;
	i=start;
	j=tail;
	x=b[i];
	do
	{
		while(b[j]>=x && j>i)
			j=j-1;
		if(j>i)
		{
			temp=b[i];
			b[i]=b[j];
			b[j]=temp;
		}
		while(b[i]<=x && i<j)
			i=i+1;
		if(i<j)
		{
			temp=b[j];
			b[j]=b[i];
			b[i]=temp;
		}
	}
	while(i!=j);
		b[i]=x;
	return i;
}

int find(int start,int tail,int k,int b[])
{
	int p,q;
	if(start==tail)
		return b[start];
	else
	{
		p=process(start,tail,b);
		q=p-start+1;
		if(k<=q)
			return find(start,p,k,b);/*在前半部分查找*/
		else
			return find(p+1,tail,k-q,b);/*在后半部分查找*/
	}
}