三者取中算法排序.c

三者取中的排序算法

/*
  Name: 排序算法 
  Copyright:LC 
  Author: 罗超 
  Date: 02-01-08 16:56
  Description: 输入若干组长度各异的待排序列，分别用快速排序算法和改进的枢轴元素三
  者取中算法对待排序列进行排序，当待排子序列长度已小于 20时，改用直接插入排序，
  利用时间函数验证三者取中算法在效率上的提高。（
  提示： 待排序列的长度一般应为 5000 以上）
*/

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define Max 100
#define Maxsize 10000000
typedef struct{
   long key;                              
   char data;                     
}Status;
typedef struct{
   Status r[Maxsize+1];               
   int length;                          
}SqList;//定义顺序表为存储结构 

SqList *CreatList(int );
SqList *Switch(SqList *,int ,int );

void Output(SqList * );//输出函数 
void InsertSort(SqList * );//直接插入排序 
void QuickSort(SqList *,int ,int );//快排核心 
void TQuickSort(SqList *,int ,int );//快排计算时间 
void TThreeSort(SqList *,int ,int );//三者取中计算时间 
void ThreeSort(SqList *,int ,int );//三者取中核心 

main()
{
   int List[Max]={0};//定义一个数组，存储输入的数据项目 
   int length;
   int i,j;
   SqList *L;//存储新建的数组 
   
   printf("输入任意组数据的长度(不超过7位的数字),空格分割，以0结束输入：\n");
   printf("控制位数\n");
   printf("1234567 1234567 1234567 1234567 1234567 1234567 1234567 1234567 1234567 \n");
   scanf("%d",&length);                        
   for(i=0;i<=Max-1&&length!=0;i++){
      List[i]=length;                        
      scanf("%d",&length);
   }//输入数据 
   
   for(j=0;j<=Max-1&&List[j];j++){             
      L=CreatList(List[j]);//新建顺序表                      
      if(List[j]<=20){                           
         printf("\n数据长度为%d,直接插入排序：\n",List[j]);
         InsertSort(L);                       
         Output(L);                             
      }//数字小于20 ，直接进行插入排序 
      else{//大于20 的时候，分别进行三者取中和快排                                   
         printf("\n数据长度为%d,快速排序排序 ：\n",List[j]);
         TQuickSort(L,1,List[j]);                  
         Output(L);                          
         printf("\n三者取中排序：\n",List[j]);
         TThreeSort(L,1,List[j]);            
         printf("排序完成\n");
         Output(L);                            
      }                                     
   }                  
   system("pause");    

}


//创建顺序表，并进行随机赋值 
SqList *CreatList(int len){             
   int i;
   SqList *L;
   srand(time(NULL));
   if(!(L=(SqList*)malloc(sizeof(SqList))))
      return 0;
   L->length=len;                       
   for(i=1;i<=len;i++){
       L->r[i].key=1+(rand()%10000000);  //随即赋值 
   }
   return L;
}

//输出函数 
void Output(SqList *L)
{                  
   int i,choose;
   printf("由于数据过大，请选择操作:\n1->打印所有值\n2->不打印 \n") ;
   scanf("%d",&choose);//读入选择 
   switch(choose){
   case 1:                               
      printf("打印所有值有：\n");
      for(i=1;i<=L->length;i++)
         printf("%d ",L->r[i].key);
      break;
   case 2:                    
      printf("不进行操作   \n");           
      break;
   default:                             
      printf("非法输入，不进行操作");
      break;
   }
   printf("\n");
}

//直接插入排序 
void InsertSort(SqList *L)
{               
   int i,j;
   clock_t start,finish;   //调用时间函数 
   double duration;          //定义持续时间 
   start=clock();
   for(i=2;i<=L->length;++i)
      if(L->r[i].key<L->r[i-1].key){      
         L->r[0]=L->r[i];          //以r[0]为标志位 
         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];       //插入到应在的位置 
      } 
   finish=clock();
   duration=(double)(finish-start)/CLOCKS_PER_SEC;
   printf("耗时%f秒\n",duration);      //输出时间 
}

//快速排序核心 
void QuickSort(SqList *L,int low,int high)
{    
   int ploc;   
   int pkey;                         
   if(low<high){
         L->r[0]=L->r[low];          //r[0]作枢轴记录 
         pkey=L->r[low].key;     //枢轴记录关键字 
         while(low<high){            
               while(low<high&&L->r[high].key>=pkey)
                      --high;                    
                      L->r[low]=L->r[high];    //移动比枢轴元素小的 到前半部分 
         while(low<high&&L->r[low].key<=pkey)
                ++low;
         L->r[high]=L->r[low]; //移动比枢轴元素小的到后半部分 
                        }
      L->r[low]=L->r[0];       
      ploc=low;   //将原来的表分裂成为两个 
      QuickSort(L,low,ploc-1);  
      QuickSort(L,ploc+1,high); //分别对前后两个部分进行快速排序    
   }    
}

//快速排序调用时间外壳 
void TQuickSort(SqList *L,int low,int high)
{
   clock_t start,finish;     //时间函数 
   double duration;             //持续时间 

   start=clock();  
   QuickSort(L,low,high);           //快速排序   
   finish=clock();
   
   duration=(double)(finish-start)/CLOCKS_PER_SEC;
   printf("耗时%f秒\n",duration);//输出计算时间 
}


//三者取中排序核心 
void ThreeSort(SqList *L,int low,int high)
{
   int ploc; 
   int pkey;                           
   if(low<high){
                L=Switch(L,low,high
                );      //选择枢轴所在 
   L->r[0]=L->r[low];           //r[0]作枢轴记录 
   pkey=L->r[low].key;     //枢轴记录关键字
    while(low<high){
         while(low<high&&L->r[high].key>=pkey)
               --high;
         L->r[low]=L->r[high];  //移动比枢轴元素小的 到前半部分 
         while(low<high&&L->r[low].key<=pkey)
               ++low;
         L->r[high]=L->r[low]; //移动比枢轴元素小的到后半部分 
     }
    L->r[low]=L->r[0];  
    ploc=low;  //将原来的表分裂成为两个 部分 
    ThreeSort(L,low,ploc-1);  
    ThreeSort(L,ploc+1,high);   //分别对前后两个部分进行快速排序     
   }    
}

//三者取中排序时间函数外壳 
void TThreeSort(SqList *L,int low,int high)
{
   clock_t start,finish;       //时间函数 
   double duration;       //持续时间 

   start=clock();  
   ThreeSort(L,low,high);      //三者取中法  
   finish=clock();
   
   duration=(double)(finish-start)/CLOCKS_PER_SEC;
   printf("耗时%f秒\n",duration);//输出计算时间 
}


//进行枢轴比较交换 
SqList *Switch(SqList *L,int low,int high)
{
   int hold; //暂存记录 
   if((L->r[low].key>=L->r[(low+high)/2].key&&L->r[(low+high)/2].key>=L->r[high].key)||(L->r[low].key<=L->r[(low+high)/2].key&&L->r[(low+high)/2].key<=L->r[high].key)){
      hold=L->r[low].key;  
      L->r[low].key=L->r[(low+high)/2].key;//枢轴调换 ，换最小 
      L->r[(low+high)/2].key=hold;
      return L; 
   }
   else if((L->r[(low+high)/2].key>=L->r[low].key&&L->r[low].key>=L->r[high].key)||(L->r[(low+high)/2].key<=L->r[low].key&&L->r[low].key<=L->r[high].key)){
      return L;          //枢轴不变 
   }
   else if((L->r[(low+high)/2].key>=L->r[high].key&&L->r[high].key>=L->r[low].key)||(L->r[(low+high)/2].key<=L->r[high].key&&L->r[high].key<=L->r[low].key)){
      hold=L->r[low].key;    
      L->r[low].key=L->r[high].key;   //枢轴调换 ，换最大 
      L->r[high].key=hold;
      return L; 
   }
}