算法课程设计.txt

这是我今年数据结构的课程设计

#include<iostream.h>
#include<time.h>
#include<stdlib.h>
int converttime1=0,converttime2,converttime3,converttime4;//定义交换次数

//直接插入排序
int *Insertionsort(int *A,int n)
{
 int j,item,i;
 for(j=2;j<=n;j++)
 {
  item=A[j];
      i=j-1;
  

  while (item<A[i])
  {
   A[i+1]=A[i];
   i--;
  }
  A[i+1]=item;
  converttime2++;
 }
 return A;
}//直接插入排序
//-----------------------------------------------------------------------

//快速排序
int Quickpass(int R[],int  low,int  high)
{
 int down,up; //initialize  flag
 down=low;up=high;R[0]=R[low]; //put benchmark record into R[0]
 while (down<up)
 {
  while((down<up)&&(R[up]>=R[0])) //scan from right to left
   up--;
  if(down<up)
   R[down++]=R[up];
  
  while((down<up)&&(R[down]<=R[0]))//scan from left to right
   down++;
  if(down<up)
   R[up--]=R[down];
  
 }
 R[down]=R[0];
 return down;
}//one time of sortion


int  *Quicksort(int R[],int low,int high)
{
 int mid;
 if (low<high)
 {
  mid=Quickpass(R,low,high);
  Quicksort(R,low,mid-1);
  Quicksort(R,mid+1,high);
  converttime1++;
 }
 return R;

}//快速排序
//-------------------------------------------------------------------------------

//冒泡排序
int *maopao(int data[],int m)
{
int i,j,temp;//data存放要排序的数据。   
                                   
   
  for(j   =   0;j<m-1;j++)//比较number-1次   
  {   
  for(i   =   0;i<m-1;i++)   
  {   
  if(data[i+1]<data[i])//交换顺序   
  {   //counttime1++;
  temp   =   data[i+1];   
  data[i+1]   =   data[i];   
  data[i]   =   temp; 
  converttime3++;
  
  }   
  }   
  }
  return data;
}
//冒泡排序
//----------------------------------------------------------------------------------


//直接选择排序
void selectsort(int s[],int m)
{
	int i,j,k;int t;
	for(i=0;i<m-1;i++)
	{
		k=i;
		for(j=i+1;j<m;j++)
			if(s[j]<s[k])k=j;
			if(k!=i)
			{
				t=s[i];
				s[i]=s[k];
				s[k]=t;
				converttime4++;
			}
	}
}
//直接选择排序
//------------------------------------------------------------------------------------


//输出限制函数
void confine(int i)
{
        
        if(i%10==0)
          cout<<endl;
}
//-------------------------------------------------------------------------------------


//主函数
void main()
{

 clock_t start,end;
 float elapsed1; //time of quicksort
 float elapsed2; //time of insertionsort
 float elapsed3;//time of maopaosort
 float elapsed4;//time of selectsort
// float elapsed4;
 const int n=20001;//数据规模
 const int m=20000;//数据规模
 int i;int w;

 cout<<"|------2006-2007数据结构课程设计---------|"<<endl;
 cout<<"|---------四种排序算法的比较-------------|"<<endl;
 cout<<"|-----------数据规模：20000--------------|"<<endl;
 cout<<"|---power by huangjianqun(02210050211)---|"<<endl;
 cout<<"  ---------------------------------------"<<endl;
 cout<<"running……"<<endl;

while(w)
{
 //产生随机数
  int sj[m];
  for(i=0;i<m;i++)
  sj[i]=rand();


 //INSERTIONSORT//计算直接插入排序的时间
    
 start=clock(); //start time
 

 int A[m];
 for(i=0;i<m;i++)
 A[i]=rand();


    Insertionsort(A,m);

 end=clock(); //finish time

 elapsed2=((float)end-start)/CLOCKS_PER_SEC;



//INSERTIONSORT


//QUICKSORT
 
 
 start=clock();//start time
    int R[n];
    for(i=1;i<=n;i++)
 R[i]=rand();

    Quicksort(R,1,n);

    end=clock(); //time finish

 elapsed1=((float)end-start)/CLOCKS_PER_SEC;
//QUICKSORT

//maopao

 start=clock();//start time
 int data[m];
 for(i=1;i<=m;i++)
	 data[i]=rand();

    maopao(data,m);

	end=clock();
	elapsed3=((float)end-start)/CLOCKS_PER_SEC;

//selectsort
  start=clock();//start time
  int s[m];
  for(i=1;i<=m;i++)
  s[i]=rand();
  selectsort(s,m);
  end=clock();
  elapsed4=((float)end-start)/CLOCKS_PER_SEC;
 cout<<"选择<7>退出;"<<endl;
 cout<<"选择<6>比较算法的交换次数"<<endl;
 cout<<"选择<5>验证selectsort的正确性"<<endl;
 cout<<"选择<4>验证maopao的正确性"<<endl;
 cout<<"选择<3>验证insertionsort的正确性"<<endl;
 cout<<"选择<2>验证quicksort的正确性"<<endl;
 cout<<"选择<1>比较算法运算时间"<<endl;
 cout<<"选择<0>产生20000 个随机数"<<endl;
 cout<<"请输入您的选择：";
 cin>>w;
 switch(w){
  case 7:break;
  case 6: cout<<"insertionsort的交换次数为："<<converttime2<<endl;
	      cout<<"quicksort的交换次数为："<<converttime1<<endl;
		  cout<<"maopaosort的交换次数为："<<converttime3<<endl;
		  cout<<"selectsort的交换次数为:"<<converttime4<<endl;
		  cout<<"通过比较可知，交换所用次数最少的是："<<"快速排序(quicksort)"<<converttime1<<"次"<<endl;
		  break;

  case 5:for(i=0;i<m;i++)
		 {
			 cout<<s[i]<<" ";
	         confine(i);
		 }

	  break;
  case 4:for(i=0;i<m;i++)
		 {
			cout<<data[i]<<" ";
	        confine(i);
		 }
	        
	  
	 break;
  case 3:for(i=0;i<m;i++)
		 {
         cout<<A[i]<<" ";
	     confine(i);
		 }
   break;
  case 2:for(i=1;i<n;i++)
		 {
         cout<<R[i]<<" ";
	     confine(i);
		 }
		 

   break;
  case 1: cout<<"insertionsort的运行时间:"<<elapsed2<<"s"<<endl;
          cout<<"quicksort的运行时间:"<<elapsed1<<"s"<<endl;
		  cout<<"maopaosort的运行时间:"<<elapsed3<<"s"<<endl;
		  cout<<"selectsort的运行时间:"<<elapsed4<<"s"<<endl;
		  cout<<"通过比较可知，排序所用时间最短的算法为快速排序(quicksort):"<<elapsed1<<"s"<<endl;
		 
		 
   break;
  case 0:for(i=0;i<m;i++)
		 {
	     cout<<sj[i]<<" ";
	     confine(i);
		 }
         break;
         

  default: cout<<"错误！请输入正确的功能序号!"<<endl;
 }
 
}
}