10.2.cpp

一个排序二叉树算法的基本实现

#include<iostream.h>
int cmp(int a,int b)
{
	if(a>b) return 1;
	else if(a==b) return 0;
	else return -1;
}
void binsertsort(int a[], int n)
{
	for(int i=1;i<=n;i++)
	{
		a[0]=a[i];
		int low=1; int high=i-1;
		while(low<=high)
		{
			int m=(low+high)/2;
			if(cmp(a[0],a[m])>0)
				low=m+1;
			else
				high=m-1;
		}
		for(int j=i-1;j>=high+1;--j)
		{
			a[j+1]=a[j];
		}
		a[high+1]=a[0];
	}
}
void twobinsertsort(int a[],int b[],int n)
{
	int first=0,final=0,j=0;
	b[0]=a[0];
	for(int i=1;i<n;i++)
	{
		if(cmp(b[0],a[i])<=0) 
		{
			if(cmp(a[i],b[final])<=0) 
			{ 
				final=(final+1)%n;
				for(j=final-1 ; cmp(a[i],b[j])<=0 ; j-- )
				b[j+1] = b[j];
				b[j+1] = a[i];
			}
			else {final=(final+1)%n; b[final]=a[i];}
		}
		else
		{
			if(cmp(a[i],b[first])>=0)
			{
				if(first==0) 
				{
					first=n-1; 
					for(int j=0;cmp(a[i],b[j])>=0;j++) 
					{
						if(j==0) b[first]=b[j];
						else b[j-1]=b[j];
					}
					b[j-1]=a[i];
				}
		        else 
				{
					first=(first-1)%n;
					for(j=first+1;cmp(a[i],b[j])>=0;j++) b[j-1]=b[j];
					b[j-1]=a[i];
				}
			}
			else 
			{ 
				if(first==0)
				{ 
				 first=n-1; b[first]=a[i];
				}
			    else first=(first-1)%n; b[first]=a[i];
			}
		}
}
	for(j=0;j<n;j++)
	{
		if(first<n)
		{a[j]=b[first]; first++;}
		else {a[j]=b[(first)%n]; first++;}
	}
}
void main()
{
	int a[10],b[10]={0},n=0;
	int x;
	cout<<"input a[10]:";
	while(n<10)
	{	
		cin>>x;			
		a[n]=x;		
		n++;
	}

	twobinsertsort(a,b,10);
	for(n=0;n<=9;n++)
		cout<<a[n]<<' ';
	cout<<endl;

}