1.cpp

选择排序,冒泡排序,快速排序等几种排序的比较

#include<iostream.h>
#include<iomanip.h>
#define  N 5
//成绩输入
void input(int stu[N] )
{   int i;
	cout<<"input 5 int numbers:"<<endl; 
	for(i=0;i<N;i++)
		cin>>stu[i];
}
//成绩输出
void output(int stu[N] )
{   int i;
	cout<<"out put:"<<endl;
	for(i=0;i<N;i++)
		cout<<setw(5)<<stu[i];
}
//对成绩顺序查找，若找到返回序号，若找不到则返回-1
int search(int stu[N],int x)
{
     int i;
	 for(i=0;i<N;)
		 if(x==stu[i])
		 {
			 return i+1;
		
		 }
		else
			i++;
	if(i>=N)
		return -1;
	else 
		return i+1;
}
//折半查找
int searchby_mid(int stu[N],int x)
{
	int mid,low=0,high=N-1;
    while(low<=high)
	{
		mid=(low+high)/2;
		if(stu[mid]<x)
			high=mid-1;
		else if(stu[mid]>x)
			low=mid+1;
		else 
		
			return mid+1;		
		
	}

	return -1;

}

//冒泡法对成绩按降序排序
void orderby_mp(int stu[N])
{
	int i,j,temp;
	for(i=0;i<N;i++)
		for(j=0;j<N-i-1;j++)
			if(stu[j]<stu[j+1])
			{
				temp=stu[j];
			    stu[j]=stu[j+1];
				stu[j+1]=temp;
			}

	cout<<endl<<"冒泡排序结果："<<endl;
	for(i=0;i<N;i++)
		cout<<setw(5)<<stu[i]<<endl;
}
//直接插入法对成绩按降序排序
void orderby_insert(int stu[N])
{
	int i,j,temp;           //temp为中间变量存放当前要插入的元素的值
	for(i=1;i<N;i++)
		if(stu[i]>stu[i-1])
		{
			temp=stu[i];

			stu[i]=stu[i-1];
			for(j=i-1;j>=0;j--)
				if(temp>stu[j])
					stu[j+1]=stu[j];
				else 
					break;
			stu[j+1]=temp;
		}
	cout<<endl<<"直接插入排序结果:"<<endl;
	for(i=0;i<N;i++)
		cout<<stu[i]<<endl;

}
//一趟快速排序
int  orderby_partition(int stu[N],int low,int high)
{
	int temp;         //temp为枢轴的值
    temp=stu[low];
	while(low<high)
	{
		while(low<high && stu[high]<temp)
			high--;
		stu[low]=stu[high];
		while(low<high && stu[low]>temp)
			low++;
		stu[high]=stu[low];
	}
	stu[low]=temp;
	return low;
}
//快速排序法才对学生成绩按降序排序
void qsort(int stu[N],int low,int high)
{
	int temp;               //temp为枢轴的位置
	if(low<high)
	{
		temp=orderby_partition(stu,low,high);
		qsort(stu,low,temp-1);
		qsort(stu,temp+1,high);
	}

}

void main( )
{
	int stu[N],x,i,j;
    input(stu);
	output(stu);
	cout<<endl<<"输入要查找的数:"<<endl;
	cin>>x;
	j=search(stu,x);
	cout<<endl<<"直接查找:"<<endl;
    if(j!=-1)
		cout<<x<<"  "<<"position:"<<j<<endl;
	else
		cout<<"not find!"<<endl;

	orderby_mp(stu);
	orderby_insert(stu);
    qsort(stu,0,N-1);
	cout<<endl<<"快速排序结果:"<<endl;
	for(i=0;i<N;i++)
		cout<<stu[i]<<endl;
    cout<<endl<<"输入要查找的数:"<<endl;
	cin>>x;
    cout<<"折半查找:"<<endl;
	j=searchby_mid(stu,x);
	if(j!=-1)
		cout<<x<<"  "<<"position:"<<j<<endl;
	else
		cout<<"not find!"<<endl;
	
	



	    

}