insertsortandheapsort.cpp

堆排序、直接插入排序算法比较!!!数据结构课程设计.实现的功能如说明所示

 #include<malloc.h>
 #include<stdio.h> 
 #include<stdlib.h> 
 #include<iostream.h> 
 #include <time.h> 


#define   max_size   2000 
typedef struct 
{ 
 int r[max_size+1];          /*数组*/
 long length;                /*长度*/
}Sqlist;                     /*线性表*/
Sqlist a,p,q;

static int bijiao1,yidong1;
static int bijiao2,yidong2;
int m=1;
                            
void insert(Sqlist *R)       /*直接插入排序*/    
{int i,j;
      bijiao1=0;yidong1=0;
for(i=2;i<=(*R).length;i++){
       bijiao1++;
       if((*R).r[i]>(*R).r[i-1])
                       /*如果当前数大于前一个数，才需要向前插入*/
  {(*R).r[0]=(*R).r[i];
                       /*给临时变量*/
       for(j=i-1;j>0&&(*R).r[0]>(*R).r[j];j--)
           {
    (*R).r[j+1]=(*R).r[j];/*向后移*/
                bijiao1++; 
                yidong1=yidong1+2;
           }
 (*R).r[j+1]=(*R).r[0];/*找到位置就插入*/
   }
 }
      cout<<"第"<<m<<"组直接插入排序的序列如下:" <<endl;
      for(i=1;i<=(*R).length;i++)
      cout<<(*R).r[i]<<" ";
	  cout<<endl;
      cout<<"第"<<m<<"组直接插入排序时，元素比较次数为:"<<bijiao1<<"次"<<endl;
      cout<<"第"<<m<<"组直接插入排序时，元素移动次数为:"<<yidong1<<"次"<<endl;
 
 }                                            
void  pushdown(int first,int last, Sqlist *A)     /*堆排序*/
{int s=first;int temp;
 
 while(s<=last/2)
       if((s==last/2)&&(last%2==0))/*r只有一个儿子*/
   { 
            if((*A).r[s]>(*A).r[2*s])
        {temp=(*A).r[s];   (*A).r[s]=(*A).r[2*s];    (*A).r[2*s]=temp;}

         s=last;
         yidong2=yidong2+2;
               bijiao2++;
         }  
        
 else if( ((*A).r[s]>(*A).r[2*s]) && ((*A).r[2*s]<=(*A).r[2*s+1]) )
                      /*左儿子和它交换*/
   {
        temp=(*A).r[s];   (*A).r[s]=(*A).r[2*s];      (*A).r[2*s]=temp;

        s=2*s;
        yidong2=yidong2+2;
              bijiao2=bijiao2+2;
   }
       else  if( ((*A).r[s]>(*A).r[2*s+1]) && ((*A).r[2*s+1]<(*A).r[2*s]) )
                           /*右儿子和它交换*/
   {
             temp=(*A).r[s];   (*A).r[s]=(*A).r[2*s+1];    (*A).r[2*s+1]=temp;

        s=2*s+1;
        yidong2=yidong2+2;
              bijiao2=bijiao2+2;
   }

   
       else
       s=last;
            
}
void sort_dui(Sqlist *A)
{   int i,temp,n=(*A).length;
    bijiao2=0,yidong2=0;
    for(i=n/2;i>=1;i--)                 /*建小顶堆*/
       pushdown(i,n,A);
    cout<<"第"<<m<<"组构造出来的初始堆为："<<endl;
    for(i=1;i<=(*A).length;i++)
      {cout<<(*A).r[i]<<" ";
      } 
	cout<<endl;
    for(i=n;i>=2;i--)
      {temp=(*A).r[1];
       (*A).r[1]=(*A).r[i];
       (*A).r[i]=temp;
       pushdown(1,i-1,A);   /*调整堆*/
       yidong2=yidong2+2;
                                
      }
    cout<<"第"<<m<<"组堆排序的序列如下:"<<endl;  
     for(i=1;i<=(*A).length;i++)
     {cout<<(*A).r[i]<<" ";
     }
	 cout<<endl;
     cout<<"第"<<m<<"组堆排序时，元素比较次数为："<<bijiao2<<"次"<<endl;
     cout<<"第"<<m<<"组堆排序时，元素移动次数为："<<yidong2<<"次"<<endl;
}


Sqlist init_data(Sqlist *B)    /*用伪随机数产生函数rand()%num来初始化第m组数据*/
 { long i;
   Sqlist L;
//char x;
//cout<<"随机输入选择‘s’"<<"  "<<"手动输入选择‘d’"<<endl;
//cin>>x;
   cout<<"请输入第"<<m<<"组排序的数目:"<<endl;
   cin>>(*B).length;
   while(!((*B).length<=2000 &&(*B).length>=1)){
       
        cout<<"!!请输入2-2000的排序数目:"<<endl;
        cin>>(*B).length;
       } 
//if(x=='d'||x=='D'){
//   cout<<"第"<<m<<"组手动输入的数据:"<<endl;
//   for( i=1;i<=(*B).length;i++){
//	  cout<<"第"<<i<<"个：";                   /*手动输入测试数据*/
//       cin>>(*B).r[i];
//       }
//    for( i=1;i<=(*B).length;i++){
//        cout<<(*B).r[i]<<" "; 
//       } 
// }
//   else if(x=='s'||x=='S'){
//     cout<<"第"<<m<<"组随机产生的数据:"<<endl;
     for( i=1;i<=(*B).length;i++)
       {
  	    (*B).r[i] = rand()%1000 ;         /*随机产生测试数据*/
          cout<<(*B).r[i]<<" "; 
     
       }
//  }
   cout<<endl;
   L=*B;
   return L;
} 



int main()
{char j='y';

cout<<"******************数据结构课程设计*****************"<<endl ;
cout<<"输入比较的组数m=："<<endl;
cin>>m;

if(m>0){
 for(m;m>=1;m--){
   p=init_data(&a);

    q=p; 
    insert(&p); 
    sort_dui(&q);
    
   cout<<"******************结果总结*********************" <<endl;
   if(bijiao1>bijiao2) cout<<"第"<<m<<"组直接插入排序比堆排序比较次数多"<<endl ;
   else if(bijiao1<bijiao2) cout<<"第"<<m<<"组直接插入排序比堆排序比较次数少"<<endl;
   else cout<<"第"<<m<<"组两种排序方法比较次数相同" <<endl;
   if(yidong1>yidong2) cout<<"第"<<m<<"组直接插入排序比堆排序移动次数多"<<endl;
   else if(yidong1<yidong2) cout<<"第"<<m<<"组直接插入排序比堆排序移动次数少"<<endl ;
   else cout<<"第"<<m<<"组两种排序方法移动次数相同"<<endl ;
   cout<<"@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@"<<endl;
 }
 
}
else cout<<"你所输入的比较次数不对"<<endl;
cout<<"继续进行下一次排序吗?(Y/N)" <<endl;
cin>>j;
while(j=='y'||j=='Y')
 {bijiao1=0,yidong1=0;
  bijiao2=0,yidong2=0;
  return (main());
 }
return 0;
}