#define MAXSIZE 10000
#define N 2000
#define SORTNUM 5
#define maxGroup 18
#define minGroup 8
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include <dos.h>
typedef int datatype[MAXSIZE+2];
void BubbleSort(long *c,long *s);
void InsertSort(long *c,long *s);
void SelectSort(long *c,long *s);
void QuickSort(long *c,long *s);
void HeapSort(long *c,long *S);
void Sift(int left,int right);
void QSort(int lo,int hi);
void Shift(int i,int j);
void Swap(int i,int j);
int  Less(int i,int j);
void RecallList();
void BeforeSort();
void InverseOrder();
void RandomizeList(int d,int isInverse);
void InitList(int n);
void Interpret(char cmd);
void readcommand(char *cmd);
void Initialization();
typedef void (*Func)(long *c,long *s);
static Func Sorts[SORTNUM]={BubbleSort,InsertSort,SelectSort,QuickSort,HeapSort};
static char *SortNames[5]={" Bubble ","Insert ","Selec ","Quick ","Heap"};
static int Mix[]={0,1,4,16,64,128,256,512,4096};

datatype data;
datatype data2;
long compCount,shiftCount;
long c,s,ts0,ts1,th0,th1,t0,t1,t2,t3;
int size,groups;
char choose;
struct  time t;
void main(){                /*主函数*/
 char cmd;
 Initialization();           /*系统初始化，显示界面*/
 do{
   readcommand(&cmd);       /*输入指令*/                                                                                              
   Interpret(cmd);            /*处理指令*/
   }while(cmd!='q'&&cmd!='Q');
  }

void Initialization(){             /*初始化函数*/
 int i,j;
 randomize();
  clrscr();
gotoxy(1,1);
       putch(0xda);
       for(i=2;i<79;i++) putch(0xc4);           /*print '-'*/
       putch(0xbf);
       for(i=2;i<25;i++)
         {
           gotoxy(1,i);putch(0xb3);          /*print '|'*/
           gotoxy(79,i);putch(0xb3);
          }
       gotoxy(1,25);
       putch(0xc0);
       for(i=2;i<79;i++) putch(0xc4);/*print '-'*/
          putch(0xd9);
gotoxy(2,2);
printf("********SortTest-1    Size(1---10000)-2    Groups(8--18)-3    Quit-q********");
gotoxy(2,3);
printf(" Command              Size=                Groups=        Time(y/n):");
gotoxy(11,3);putch(0x10);
gotoxy(3,4);                                     /*表格起始点*/
       putch(0xda);
       for(i=2;i<75;i++) putch(0xc4);           /*print '-'*/
       putch(0xbf);
       for(i=5;i<25;i++)
         {
           gotoxy(3,i);putch(0xb3);          /*print '|'*/
           gotoxy(77,i);putch(0xb3);
          }
       gotoxy(3,25);
       putch(0xc1);
       for(i=2;i<75;i++) putch(0xc4);/*print '-'*/
          putch(0xc1);

        
gotoxy(16,5);
printf("compparisonCount                      shiftCount");
gotoxy(8,6);
for(j=0;j<2;j++){
  for(i=0;i<5;i++)
    printf("%s",SortNames[i]);
  printf("  ");
 } 
gotoxy(4,5);                                   /*第一列起点*/
printf("Mix ");putch(0xb3);gotoxy(40,5);putch(0xb3);
gotoxy(8,6);putch(0xb3);gotoxy(40,6);putch(0xb3);   
}

void readcommand(char *cmd){                 /*输入指令*/
 
 gotoxy(12,3);
 do{*cmd=getchar();}while(*cmd!='1'&&*cmd!='2'&&*cmd!='3'&&*cmd!='q'&&*cmd!='Q');
 
 }


void Interpret(char cmd){               /*处理指令*/
  int i,j,n,k , m=0,flag=0,p;
long tt,tm0,tm1;
  switch(cmd){
     case'1':
             flag=1;

             for(i=0;i<=groups-1;i++){
               if(i<groups/2){
                 RandomizeList(i,0);             /*对正序表作第i级打乱*/                       
                 gotoxy(5,i+7);printf(" %d ",m++);putch(0xb3);
           }
               else{
                 RandomizeList(groups-i-1,1);        /*对逆序表作第i级打乱*/
                 gotoxy(5,i+7);
         if(groups%2==0){printf("-%d ",(m--)-1);putch(0xb3);}
         else {printf("-%d ",m--);putch(0xb3);}
               }
               for(j=0;j<SORTNUM;j++){                                             /*分别测试排序算法*/
                  RecallList();
          gettime(&t);th0=t.ti_hund;ts0=t.ti_sec;tm0=t.ti_min;            /*获取系统时间*/
            t0=(tm0*60+ts0)*1000+th0;
                  for(p=0;p<1000;p++){
                    (*Sorts[j])(&c,&s);
            RecallList();
           }
          gettime(&t);th1=t.ti_hund;ts1=t.ti_sec;tm1=t.ti_min;        /*获取系统时间*/
          t1=(tm1*60+ts1)*1000+th1;
          tt=t1-t0;/*-tsum;*/
         if(choose!='y'){      /*选择显示比较次数和移动次数*/
            gotoxy(15+(j-1)*6,7+i);printf("%6ld ",c);
                    gotoxy(49+(j-1)*6,7+i);printf("%6ld",s);
            gotoxy(40,i+7);putch(0xb3); 
         }
         if(choose=='y'){                  /*显示排序时间*/
           if(flag==0)clrscr();
/**************************************************************************/
gotoxy(1,1);
       putch(0xda);
       for(p=2;p<79;p++) putch(0xc4);           /*print '-'*/
       putch(0xbf);
       for(p=2;p<25;p++)
         {
           gotoxy(1,p);putch(0xb3);          /*print '|'*/
           gotoxy(79,p);putch(0xb3);
          }
       gotoxy(1,25);
       putch(0xc0);
       for(p=2;p<79;p++) putch(0xc4);/*print '-'*/
          putch(0xd9);
gotoxy(2,2);
printf("********SortTest-1    Size(1---10000)-2    Groups(8--18)-3    Quit-q********");
gotoxy(2,3);
printf(" Command  %c          Size=%d             Groups=%d        Time(y/n):%c",cmd,size,groups,choose);
gotoxy(11,3);putch(0x10);
gotoxy(3,4);                                     /*表格起始点*/
       putch(0xda);
       for(p=2;p<75;p++) putch(0xc4);           /*print '-'*/
       putch(0xbf);
       for(p=5;p<25;p++)
         {
           gotoxy(3,p);putch(0xb3);          /*print '|'*/
           gotoxy(77,p);putch(0xb3);
          }
       gotoxy(3,25);
       putch(0xc1);
       for(p=2;p<75;p++) putch(0xc4);/*print '-'*/
          putch(0xc1);

        
gotoxy(16,5);
printf("                  Time(*1000)/ms                   ");
gotoxy(9,6);
  for(p=0;p<5;p++)
    printf("   %s    ",SortNames[p]);
gotoxy(27+(j-1)*13,7+i);printf("%ld",tt);
 
gotoxy(4,5);                                   /*第一列起点*/
printf("Mix ");putch(0xb3);
gotoxy(8,6);putch(0xb3);
/*************************************************************************/
               }}        
              }                                                              
         break;

     case'2':gotoxy(29,3);             /*输入测试有序表的长度*/
             scanf("%d",&n);size=n;
         gotoxy(70,3);
         getchar();
         choose=getchar();
             if(n<1)n=1;
             if(n>10000)n=10000;
             InitList(n);
             break;
     case'3':                                 /*输入测试组数*/
         gotoxy(52,3);
             scanf("%d",&groups);
             if(groups<minGroup)groups=minGroup;
             if(groups>maxGroup)groups=maxGroup;
             break;
            }
  }


void InitList(int n){                          /*构造顺序表*/
   int i;
   if(n<1)size=0;
   else{
     if(n>MAXSIZE)n=MAXSIZE;
     for(i=1;i<=n;i++)data[i]=data2[i]=i;
     size=n;
     }
     compCount=shiftCount=0;
 }

void RandomizeList(int d,int isInverse){              /*对可排序表进行d次随机打乱*/
  int a,b,c,i;
  if(isInverse)InverseOrder();
  else InitList(size);
  for(i=1;i<=Mix[d];i++){
    a=random(size);
    b=random(size);
    c=a;a=b;b=c;
    c=data[a+1];data[a+1]=data[b+1];data[b+1]=c;
  }
   for(i=1;i<=size;i++)
     data2[i]=data[i];
 }

void InverseOrder(){                                /*将可排序表置为逆序*/
  int i;
  for(i=1;i<=size;i++)data[i]=data2[i]=size-i+1;
 }
     

void BeforeSort(){                                   /*每个排序算法在入口处调用*/
   compCount=shiftCount=0;
  }
 
void RecallList(){                /*恢复最后一次用RandomizeList随机打乱后的可排序表*/
   int i;
   for(i=1;i<=size;i++)
     data[i]=data2[i];
  }

int Less(int i,int j){                  /*比较两个元素大小*/
  compCount++;
  if(data[i]<data[j])return 1;
  else return 0;
}
 
void Swap(int i,int j){                  /*交换两个元素*/
 int a;
 a=data[i];data[i]=data[j];data[j]=a;
 shiftCount=shiftCount+3;
}
  
void Shift(int i,int j){                 /*元素赋值*/
      data[j]=data[i];
      shiftCount++;
   }

void BubbleSort(long *c,long *s){         /*冒泡排序*/
    int swapped,i,z;
     BeforeSort();
     do{
        swapped=0;
        for(i=1;i<=size-1;i++)
          if(Less(i+1,i)){Swap(i+1,i);swapped=1;}
       }while(swapped);
     *c=compCount;*s=shiftCount;th1-=th0;
   }

void InsertSort(long *c,long *s){       /*插入排序*/
    int i,j;
    BeforeSort();
   for(i=2;i<=size;i++){
      Shift(i,0);j=i-1;
      while(Less(0,j)){Shift(j,j+1);j--;}
      Shift(0,j+1);
     }
    *c=compCount;*s=shiftCount;
   }

void SelectSort(long *c,long *s){           /*选择排序*/
    int i,j,min;
    BeforeSort();
    for(i=1;i<=size-1;i++){
         min