/*
  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; 
   }
}