sort.cpp

航空订票信息系统很好的一个用C篇的,希望大家下载交流

#include"SortHead.h"


void main()
{
	int flag;
	SqList L;

while((flag=Menu())<6)
{ 
  if(flag!=0)   
  Getdata(L);
  printf("\n正在进行排序...");
  begin=clock();
  switch(flag)
  {	
    case 0: SystemInfo();     break;
	case 1:Insertsort(L);     break;
	case 2:QuickSort (L);     break;
//	case 3: ShellSort(L);     break;
	case 3:SelectSort(L);     break;
	case 4:  HeapSort(L);     break;
	case 5: MergeSort(L);     break;
//	case 7:Bubble_sort(L);    break;		
	case 6:printf("按Enter键系统退出..."); 
		   getchar(); break;
	default:exit(0);
	}
  	end=clock();
	if(flag!=0)
	show(L,flag);

        printf("\n\n\n任意键继续...");
        getchar();
		putchar(10);
}

}







int InitList(SqList &L,int size)
{
	L.r=(RecordType *)malloc((size+1)*sizeof(RecordType));
	if(!L.r) exit(1);
	L.length=size;
	L.pos=1;
	return OK;
}


int Getdata(SqList &L)
{
 int i;
 int size;
 	printf("\n\t\t\t    要排序的数据个数：");
	scanf("%d",&size);
	InitList(L,size);
    srand(time(NULL));     
	for (i=1;i<=size;i++)
	{    
		L.r[i].key= rand();
	
	}
	printf("\n\n随机数据生成完毕，是否显示？（Y/N）");
	fflush(stdin);
	char ch=getchar();
	if(ch=='Y'||ch=='y')
	{
	for (i=1;i<=size;i++)
	printf("%6d  ",L.r[i].key);
	}
	fflush(stdin);
	printf("\n按Enter键开始排序...");
	getchar();
   return OK;
}


void show(SqList L,int flag)
{
  int i;
  char ch,name[20];
  FILE *fp;

	 printf("\n\n排序执行完毕！花费时间: %.5lf 秒\n",(double)(end - begin) / CLOCKS_PER_SEC);

     fflush(stdin);
	 printf("\n是否显示并保存结果?（Y/N）");
     ch=getchar();
   if(ch=='Y'||ch=='y')
   {
	 switch(flag)
	 {
	 case 1 : strcpy(name,"插入排序结果.txt") ;break;   
	 case 2 : strcpy(name,"快速排序结果.txt") ;break;  
	 case 3 : strcpy(name,"希尔排序结果.txt") ;break;  
	 case 4 : strcpy(name,"选择排序结果.txt") ;break;  
	 case 5 : strcpy(name,"堆  排序结果.txt") ;break;  
	 case 6 : strcpy(name,"归并排序结果.txt") ;break;  
	 case 7 : strcpy(name,"冒泡排序结果.txt") ;break;  
	 default: strcpy(name,"未知排序结果.txt") ;
	 }
	 fp=fopen(name,"w"); 
	 fprintf(fp,"排序执行时间: %.5lf 秒\n\n\t\t\t",(double)(end - begin) / CLOCKS_PER_SEC);
	 fprintf(fp,"%d个数据排序结果为:\n\n",L.length);
	 for(i=1;i<=L.length;i++)
	 {
	 fprintf(fp,"%-7d",L.r[i]);
	 printf("%6d  ",L.r[i]);
	 if(i%17==0)	 
   	 fputc(10,fp);

	 
	 }
	 fprintf(fp,"");	
	 fclose(fp);
	 printf("\n\n\t\t\t    文件已保存为：\"%s\"\n",name);
	 fflush(stdin);
   }
   fflush(stdin);
   return ;
}



void Insertsort(SqList &L)        
{
	int i,j;
  for(i=2;i<=L.length;i++)
        if(L.r[i].key<L.r[i-1].key) 
        { 
          L.r[0]=L.r[i];            
          L.r[i]=L.r[i-1];         
          for (j=i-2;L.r[0].key<L.r[j].key;j--)
                  L.r[j+1]=L.r[j];
          L.r[j+1]=L.r[0];
        }
} 





void ShellSort(SqList &L)
{
    	ShellArray(L);
                                                 
       for(int k=1;k<shell_len;k++)
        ShellInsert(L,L.length,shell_add_arr[k]);                
}                                               

void ShellArray(SqList L)
{
	int i=1,j=1;
    shell_add_arr[0]=1;
	while(j<=L.length&&j<=MAXNUM)
	{
    	shell_add_arr[i++]=j;
		j+=2;
		shell_len++;
	}

	

}

void ShellInsert(SqList &L,int len,int add) 
   {   
	  int i,j;
      for(i=add+1;i<=len; i++)
      {         
         L.r[0]=L.r[i];
         for(j=i-add; j>0 &&(L.r[0].key<L.r[j].key); j-=add)
	      L.r[j+add]=L.r[j];
          L.r[j+add]=L.r[0];
       }
}






void QuickSort ( SqList  &L) 
{
        QSort (L,1,L.length );
}

void QSort ( SqList  &L,  int low, int high ) 
{
    int pbase;       
    if ( low < high) {				  
       pbase= Partition ( L, low, high ); 
       QSort ( L, low, pbase-1);	    
       QSort ( L, pbase+1, high );
    }
}

int Partition(SqList &L,int low,int high)
{          
         KeyType   pbase;
		 int i=low,j=high;
         pbase=L.r[low].key;                                             
         while(i<j)
		 { 	                                                
        	while(L.r[j].key>=pbase&&j>i ) j--;
	        if(i<j) L.r[i++]=L.r[j];                                 
	                                                 
	        while(L.r[i].key<=pbase&&j>i )  i++;
	        if(i<j) L.r[j--]=L.r[i];                                                 
	}
       L.r[i].key=pbase;
       return i;                                                             
}      

                                                                      



void SelectSort(SqList &L)
{   int i,j,k,tem;  
                               
    for (i=1; i<L.length+1; ++i)
    {                                                  
       k=i;   

       for(j=i+1;j<L.length+1; j++)
            if (L.r[j].key<L.r[k].key) 
				k=j; 
       if(k!=i)
	   {
		   tem=L.r[i].key;L.r[i].key=L.r[k].key;L.r[k].key=tem;
	   }
    }  
}




void HeapSort(SqList &H)
{      
	int i;
	RecordType tem;                                      
    for (i=H.length/2 ; i>0 ; i--)                    
           HeapAdjust(H,i,H.length);
    for (i=H.length ; i>1 ; i--)
    {                                                    
        tem=H.r[1]; 
		H.r[1]=H.r[i];
		H.r[i]=tem; 
        HeapAdjust(H,1,i-1);                         
     }
}

void HeapAdjust(SqList &H, int s , int m)
{   
	int j;
   RecordType rc = H.r[s];                                               
    for (j=2*s ; j<=m ; j*=2 )                                  
	{
	   if (j<m && (H.r[j+1].key>H.r[j].key)) ++j ; 
                                                              
        if (H.r[j].key<=rc.key) break;                     
        H.r[s] = H.r[j] ;                                     
        s=j;
	}
    H.r[s] = rc;                                                      
}   




void MergeSort(SqList &L)
{                                                                            
    int i;
	printf("\n");
    for(i=1;i<L.length;i*=2) 
	
		MergePass(L,L.length,i);                                                                                                                                                        
}                                                                               

void MergePass(SqList &L,int length , int len)
{                                                                   
  int i;
  for (i=1;i+2*len-1<=length;i=i+2*len)
 
	 Merge(L,i,i+len-1,i+2*len-1);                             
                                                                   
     
 if (i+len-1<length)                                                    
          Merge(L,i,i+len-1,length);
                                       
  }
  

void Merge(SqList &L,int low,int mid,int high)
{  
	
   int i=low,j=mid+1,pos=0,k; 
   RecordType *base;
   base=(RecordType *)malloc(sizeof(RecordType)*(high-low+1));
   while(i<=mid&&j<=high)
   {                                                               
	   *(base+pos++)=(L.r[i].key<=L.r[j].key)?L.r[i++]:L.r[j++];
     }
 	                                                                  
    while(i<=mid )                                                         
		*(base+pos++)= L.r[i++]; 
    while(j<=high ) 
		*(base+pos++)= L.r[j++]; 
	for(k=0,i=low;k<pos;k++,i++)
		 L.r[i]= *(base+k); 

	free(base);

}  
   

void Bubble_sort(SqList &L)
{  
   KeyType x;
   int flag;
   for(int i=1;i<L.length;i++)
   {  
	   flag=0;                                  
       for ( int j=L.length-1; j>=i; j--)
            if(L.r[j+1].key<L.r[j].key)
			{ 
				flag=1; 
				x=L.r[j].key;
                L.r[j].key=L.r[j+1].key;
                L.r[j+1].key=x;
			}
        if(flag==0) break;
   }
}

int Menu(){
	int choice;
	puts("     \n\t=========================================================");
	puts("\n                        〓〓〓  综合排序算法  〓〓〓\n");

	puts("                        ※  Copyright ☆ XieGang  ※   ");
	puts("     \t=========================================================");
	printf("\n\t\t           0---------------系统信息\n      ");
    printf("\n\t\t           1---------------插入排序\n      ");
	printf("\n\t\t           2---------------快速排序\n      ");
//	printf("\n\t\t           3---------------希尔排序\n      ");
	printf("\n\t\t           3---------------选择排序\n      ");
	printf("\n\t\t           4---------------堆  排序\n      ");
	printf("\n\t\t           5---------------归并排序\n      ");
//	printf("\n\t\t           7---------------冒泡排序\n      ");
	printf("\n\t\t           6---------------退出程序\n\n ");
	puts("     \t==========================================================\n");
	printf("\t\t\t\t请选择: ");
	fflush(stdin);
	scanf("%d",&choice);
	fflush(stdin);
	return choice;
}
        
void SystemInfo(){
	FILE *fp;
	if(!(fp=fopen("系统信息.txt","r")))
	{
		puts("说明文件丢失！");
			return ;
	}
	puts("\n\n\n\n");
	puts("--------------------------------------------------------------------------------");
	puts("                          〓〓〓 系统信息 〓〓〓\n  ");
	puts("--------------------------------------------------------------------------------");	
	while(!feof(fp))
		putchar(fgetc(fp));
	
	putchar(10);
	puts("--------------------------------------------------------------------------------\n");
}