sort.cpp

职工管理系统：包括职工查找、排序、编辑等

#include "string.h"
#include "employee.h"

//========================================冒泡排序==============================================
void BubbleSort::sortf(Employee *p,int size)
{
    char name[20];
	char sex;
	char edu_level;       
	char duty;        
	int  year_Born;     
	int  month_Born;    
	int  year_W;   
	int  month_W;   
	char tel[20];     

	for(int i=1;i<size;i++)
	{
	   for(int j=0;j<size-i;j++) 
		   if(strcmp(p[j].name,p[j+1].name)>0)                //按照职工姓名的字典顺序排序;
		   {     
			                                                        //换姓名
                  strcpy(name,p[j].name);
				  strcpy(p[j].name,p[j+1].name);
				  strcpy(p[j+1].name,name);
                                                                    //换性别
                  sex=p[j].sex;
				  p[j].sex=p[j+1].sex;
				  p[j+1].sex=sex;
				                                                    //换学历
				  edu_level=p[j].edu_level;
				  p[j].edu_level=p[j+1].edu_level;
				  p[j+1].edu_level=edu_level;
				                                                    //换职务
				  duty=p[j].duty;
				  p[j].duty=p[j+1].duty;
				  p[j+1].duty=duty;
				                                                    //换出生年份
				  year_Born=p[j].year_Born;
				  p[j].year_Born=p[j+1].year_Born;
				  p[j+1].year_Born=year_Born;
				                                                    //换出生月份
				  month_Born=p[j].month_Born;
				  p[j].month_Born=p[j+1].month_Born;
				  p[j+1].month_Born=month_Born;
				                                                    //换工作年份
				  year_W=p[j].year_W;
				  p[j].year_W=p[j+1].year_W;
				  p[j+1].year_W=year_W;
				                                                    //换出生月份
				  month_W=p[j].month_W;
				  p[j].month_W=p[j+1].month_W;
				  p[j+1].month_W=month_W;
				                                                    //换电话号码
				  strcpy(tel,p[j].tel);
				  
				  strcpy(p[j].tel,p[j+1].tel);
		   }
	}	   
}
//====================================折半查找排序============================================
void InsertSort::sortf(Employee *p,int size)
{   
	
    int low,high,m;
	char temp[20];                                                            //姓名临时储存变量;
	char sex;                                                                 //性别临时储存变量;
	char edu_level;                                                           //学历临时储存变量;      
	char duty;                                                                //职务临时储存变量;     
	int  year_Born;                                                       //出生年份临时储存变量;    
	int  month_Born;                                                      //出生月份临时储存变量;   
	int  year_W;                                                          //工作年份临时储存变量; 
	int  month_W;                                                         //工作月份临时储存变量; 
	char tel[20];                                                         //电话号码临时储存变量;  
	
	for (int i=1; i<size; ++i )  
    {  
		strcpy(temp,p[i].name);                                //将第i个职工的姓名储存临时变量中; 
		sex=p[i].sex;                                        //将第i个职工的性别储存的临时变量中; 
		edu_level=p[i].edu_level;		                     //将第i个职工的学历储存的临时变量中; 
		duty=p[i].duty;			                             //将第i个职工的职务储存的临时变量中; 
		year_Born=p[i].year_Born;	                     //将第i个职工的出生年份储存的临时变量中; 
		month_Born=p[i].month_Born;	                     //将第i个职工的出生月份储存的临时变量中; 
		year_W=p[i].year_W;	                             //将第i个职工的工作年份储存的临时变量中; 
		month_W=p[i].month_W;                            //将第i个职工的工作月份储存的临时变量中; 
		strcpy(tel,p[i].tel);			                 //将第i个职工的电话号码储存的临时变量中; 

		low = 0; high = i-1;  
		while (low<=high) 			
		{   
			m = (low+high)/2;                                                   //折半 
			if(strcmp(temp,p[m].name)<0)   
				high = m-1;                                                     //在低半区			
			else   
				low = m+1;                                                      //在高半区			
		}  
		for(int j=i-1; j>=high+1; --j )  
		{                                                                       // 后移1位
			strcpy(p[j+1].name,p[j].name); 
			p[j+1].sex  =p[j].sex;
			p[j+1].edu_level=p[j].edu_level;
			p[j+1].duty =p[j].duty;
			p[j+1].year_Born  =p[j].year_Born;
			p[j+1].month_Born =p[j].month_Born;
			p[j+1].year_W =p[j].year_W;
			p[j+1].month_W=p[j].month_W;
			strcpy(p[j+1].tel,p[j].tel);
		}
         // 插入
	 	 strcpy(p[high+1].name,temp); 
		 p[high+1].sex  =sex; 
		 p[high+1].edu_level=edu_level; 
         p[high+1].duty =duty;
         p[high+1].year_Born  =year_Born;
		 p[high+1].month_Born =month_Born;
		 p[high+1].year_W =year_W;
		 p[high+1].month_W=month_W;
		strcpy(p[high+1].tel,tel);
	} //end for
}

//=====================================快速排序===============================================
int  QuickSort::Partition (Employee *p, int low, int high)        
{   
	char temp[20];                                            //储存名字
	char sex;                                                 //储存性别
	char edu_level;                                           //储存学历
	char duty;                                                //储存职务
	int  year_Born;                                           //储存出生年
	int  month_Born;                                          //储存出生月
	int  year_W;                                              //储存工作年
	int  month_W;                                             //储存工作月
	char tel[20];                                             //储存电话号码

	strcpy(temp,p[low].name); 
	sex  =p[low].sex;                                          //将第i个职工的性别储存临时变量中; 
	edu_level=p[low].edu_level;		                           //将第i个职工的学历储存临时变量中; 
	duty =p[low].duty;		                                   //将第i个职工的职务储存临时变量中; 
	year_Born  =p[low].year_Born;                          //将第i个职工的出生年份储存临时变量中; 
	month_Born =p[low].month_Born;                         //将第i个职工的出生月份储存临时变量中; 
	year_W =p[low].year_W;                                 //将第i个职工的工作年份储存临时变量中; 
	month_W=p[low].month_W;                                //将第i个职工的工作月份储存临时变量中; 
	strcpy(tel,p[low].tel);			                       //将第i个职工的电话号码储存临时变量中; 
	
	char pivotkey[20] ;
	strcpy(pivotkey,p[low].name);                          
	while(low<high)                                               // 从表的两端交替地向中间扫描			
	{                                               
		while(low<high&&strcmp(p[high].name,pivotkey)>=0)
			--high;                                      
		strcpy(p[low].name ,p[high].name); 
		p[low].sex=p[high].sex;            
		p[low].edu_level=p[high].edu_level;
		p[low].duty=p[high].duty;
		p[low].year_Born=p[high].year_Born;
		p[low].month_Born=p[high].month_Born;
		p[low].year_W=p[high].year_W;
		p[low].month_W=p[high].month_W;
		strcpy(p[low].tel,p[high].tel);

		while(low<high&&strcmp(p[low].name,pivotkey)<=0)
			++low; 
		
		strcpy(p[high].name, p[low].name);                 // 将比枢轴记录小的记录移到低端
		p[high].sex=p[low].sex;            
		p[high].edu_level=p[low].edu_level;
		p[high].duty=p[low].duty;
		p[high].year_Born=p[low].year_Born;
		p[high].month_Born=p[low].month_Born;
		p[high].year_W=p[low].year_W;
		p[high].month_W=p[low].month_W;
		strcpy(p[high].tel,p[low].tel);
	} 
	
	strcpy(p[low].name, temp);
	p[low].sex  =sex;
	p[low].edu_level=edu_level;
	p[low].duty =duty;
	p[low].year_Born  =year_Born;
	p[low].month_Born =month_Born;
	p[low].year_W =year_W;
	p[low].month_W=month_W;
	strcpy(p[low].tel,tel);
	return low;                                     
}    
 
void QuickSort::QSort (Employee *p, int low, int high)
{     
	                                                                         //进行快速排序                                              
		if(low < high)                                                       // 长度大于1                                  
		{                                               
			int pivot = Partition(p, low, high);                          // 中转轴				
			QSort(p, low, pivot-1);                                       // 对低子表递归排序			
			QSort(p, pivot+1, high);                                      // 递归排序				
		}                                               
}  
 
void QuickSort::sortf(Employee * p,int size)
{     
		QSort(p, 0, size-1);                            
}

//=========================================堆排序===============================================
void HeapSort::HeapAdjust (Employee *p, int s, int m)
{ 
	char rc[20] ;
	char sex;
	char duty;   
	char edu_level;      
	int  year_Born;     
	int  month_Born;    
	int  year_W;    
	int  month_W;   
	char tel[20];     

	strcpy(rc,p[s].name);
	sex=p[s].sex;
    edu_level=p[s].edu_level;
	duty=p[s].duty;
	year_Born=p[s].year_Born;
	month_Born=p[s].month_Born;
	year_W=p[s].year_W;
	month_W=p[s].month_W;
	strcpy(tel,p[s].tel);
	
	for (int j=2*s+1; j<=m; j=2*j+1 )                                     //名字字典顺序向下筛选			
	{             
		if(j<m && strcmp(p[j].name,p[j+1].name)<0)
			j++;                                                          // 较大的下标			
		if( strcmp(rc,p[j].name)>=0) break;  
				
		strcpy(p[s].name,p[j].name);
		p[s].sex=p[j].sex;
		p[s].edu_level=p[j].edu_level;
		p[s].duty=p[j].duty;
		p[s].year_Born=p[j].year_Born;
		p[s].month_Born=p[j].month_Born;
		p[s].year_W=p[j].year_W;
		p[s].month_W=p[j].month_W;
		strcpy(p[s].tel,p[j].tel);

		s = j;                   
	}                                       
	strcpy(p[s].name,rc);                                                        // 插入 
	p[s].sex=sex;
	p[s].edu_level=edu_level;
	p[s].duty=duty;
	p[s].year_Born=year_Born;
	p[s].month_Born=month_Born;
	p[s].year_W=year_W;
	p[s].month_W=month_W;
	strcpy(p[s].tel,tel);
}  
                              
void HeapSort::sortf(Employee *p,int size)
{   
	char temp[20];
	char sex;
	char duty;   
	char edu_level;      
	int  year_Born;     
	int  month_Born;    
	int  year_W;    
	int  month_W;   
	char tel[20];     
	
	for ( int i=size/2-1; i>=0; i-- )	
		HeapAdjust ( p, i, size-1 );               
	
	for ( i=size-1; i>0; i-- ) 
	{   
		                                  //堆顶记录和当前未经排序子序列中最后一个记录相互交换;                        
		strcpy(temp,p[0].name);
		strcpy(p[0].name,p[i].name);
		strcpy(p[i].name,temp);
         
		sex=p[0].sex;
		p[0].sex=p[i].sex;
		p[i].sex=sex;
	
		edu_level=p[0].edu_level;
		p[0].edu_level=p[i].edu_level;
		p[i].edu_level=edu_level;
	
		duty=p[0].duty;
		p[0].duty=p[i].duty;
		p[i].duty=duty;
	
		year_Born=p[0].year_Born;
		p[0].year_Born=p[i].year_Born;
		p[i].year_Born=year_Born;
	
		month_Born=p[0].month_Born;
		p[0].month_Born=p[i].month_Born;
		p[i].month_Born=month_Born;
	
		year_W=p[0].year_W;
		p[0].year_W=p[i].year_W;
		p[i].year_W=year_W;
	
		month_W=p[0].month_W;
		p[0].month_W=p[i].month_W;
		p[i].month_W=month_W;
	
		strcpy(tel,p[0].tel);
		strcpy(p[0].tel,p[i].tel);
		strcpy(p[i].tel,tel);

		HeapAdjust(p, 0, i-1);                                                // 重新调整   
	}    
}