#include<stdio.h> 
#include<stdlib.h>
#include<conio.h>
#include<time.h>
#define MAXSIZE 5000
typedef int KeyType;
int count1=0,count2=0;
int chishu1=0,chishu2=0,chishu3=0,chishu4=0;
typedef struct{
	KeyType key;
	
}RedType;
typedef struct {
	RedType *r;
	int length;
}Sqlist;
void InitSqlist(Sqlist *L){
	//构造一个新的线性表L
    (*L).r=(RedType *)malloc(MAXSIZE * sizeof(RedType));//分配内存
    if (!(*L).r) 
      exit(-1);//出错退出
    (*L).length=0;//空表长度为0；
}
void CreatSqlist(Sqlist &L){
	int i;
	srand(time(NULL));
	for(i=1;i<10;i++){
	L.r[i].key=1+rand()%70;	
	L.length++;
	}
	
	
}
void CopySqlist(Sqlist L,Sqlist &L1){
	int i;
	L1.length=0;
	for(i=1;i<=L.length;i++)
	L1.r[i].key=L.r[i].key;
	L1.length=L.length;
}
void OutputSqlist(Sqlist L1 ){
	int i;
		for(i=1;i<=L1.length;i++){
		printf("%5d",L1.r[i].key);
		if(i%6==0)
		printf("\n"); 
}
}
int LT(KeyType e1,KeyType e2){
	if(e1<e2)
	return 1;
	else
	return 0;
}
void Swap(RedType &e1,RedType &e2){
	RedType e;
	e=e1;
	e1=e2;
	e2=e;
	
}
void InsertSort(Sqlist &L){
	int i,j;
	for(i=2;i<=L.length;i++)
	if(LT(L.r[i].key,L.r[i-1].key)){
		count1++;
		count2++;
		L.r[0]=L.r[i];
		L.r[i]=L.r[i-1];
		for(j=i-2;LT(L.r[0].key,L.r[j].key);j--){
			count1++;
		   count2++;
		L.r[j+1]=L.r[j];
	}
		L.r[j+1]=L.r[0];
		chishu1++;
		printf("\n第%d趟排序：\n",chishu1);
		OutputSqlist(L);
		count2++;
	}
}
/////////////////////////////////
void  ShellInsert(Sqlist &L,int dk ){
	int i,j;
	for(i=dk+1;i<=L.length;i++)
	if(LT(L.r[i].key,L.r[i-dk].key)){
		count1++;
		L.r[0]=L.r[i];
		for(j=i-dk;j>0&&LT(L.r[0].key,L.r[j].key);j=j-dk){
		count1++;
		count2++;
		L.r[j+dk]=L.r[j];
	}
		L.r[j+dk]=L.r[0];
	}
	chishu2++;
	    printf("\n第%d趟排序：\n",chishu2);
		OutputSqlist(L);
	count1++;
	
}
void ShellSort(Sqlist &L,int dlta[],int t){
	int k;
	for(k=0;k<t;k++)
	ShellInsert(L,dlta[k]);
	
	
}
////////////////////////////////
int Partition(Sqlist &L,int low,int high){
    int   pivotkey;

	L.r[0]=L.r[low];
	pivotkey=L.r[low].key;
	while(low<high)
{
	while(low<high&&L.r[high].key>=pivotkey){
	count1++;
	--high;
    }
    L.r[low]=L.r[high];
    count2++;
	while(low<high&&L.r[low].key<=pivotkey){
	++low;
	count1++;
	}
	
	L.r[high]=L.r[low];
	count2++;
}
L.r[low]=L.r[0];
count2++;
chishu3++;
	    printf("\n第%d趟排序：\n",chishu3);
		OutputSqlist(L);
return low;

}
void QSort(Sqlist &L,int low,int high){
	int pivotloc;
	
	if(low<high){
		pivotloc=Partition(L,low,high);
		QSort(L,low,pivotloc-1); 
		QSort(L,pivotloc+1,high); 
		
	}
}
void QickSort(Sqlist &L){
	QSort(L,1,L.length);
	
}
/////////////////////////////////
void HeapAdjust(Sqlist &H,int s,int m){
    RedType	 rc;
    int j;
    rc=H.r[s];
    for(j=2*s;j<=m;j=j*2){
    	if(j<m&&LT(H.r[j].key,H.r[j+1].key)){
		count1++;
    	j++;
       }
    	if(!LT(rc.key,H.r[j].key)){
		count1++;
    	break;
       }
    	H.r[s]=H.r[j];
    	s=j;// for循环 
    	
	}
	H.r[s]=rc;
	count2++; 
	
}
void HeapSort(Sqlist &H){
	int i;
	
	
	for(i=H.length/2;i>0;i--)
	HeapAdjust(H,i,H.length);
	for(i=H.length;i>1;i--){
		Swap(H.r[1],H.r[i]);
		chishu4++;
	    printf("\n第%d趟排序：\n",chishu4);
		OutputSqlist(H);
		count2++;
		HeapAdjust(H,1,i-1);
	}
}
/////////////////////////////
int main(){
	Sqlist L,L_BAK;
	int select,flag=1,t,dlta[MAXSIZE];
	double duration;
	clock_t start,finish;
	InitSqlist(&L);
	InitSqlist(&L_BAK);
	CreatSqlist(L_BAK);
	t=0;
	dlta[0]=L_BAK.length/2;
	while(dlta[t]>1){
		dlta[t+1]=dlta[t]/2;
		t++;
	}
	OutputSqlist(L_BAK);
	while(flag)
  {
  	CopySqlist(L_BAK,L);
  	count1=0;
  	count2=0;
  	//OutputSqlist(L);
  	printf("\n请选择：\n");
  	printf("1.InsertSort                   \n");
  	printf("2.ShellSort                   \n");
  	printf("3.QuickSort                   \n");
  	printf("4.HeapSort                   \n");
  	printf("5.Exit                   \n");
  	scanf("%d",&select);
  	switch(select){
	  
  	case 1: printf("\n Now is in InsertSort............");
  			start=clock();
  			InsertSort(L);
  			finish=clock();
  			break;
  	case 2: printf("\n Now is in ShellSort............");
  			start=clock();
  			ShellSort(L,dlta,t+1);
  			finish=clock();
  			break;
  	case 3: printf("\n Now is in QuickSort............");
  			start=clock();
  			QickSort(L);
  			finish=clock();
  			break;
  	case 4: printf("\n Now is in HeapSort............");
  			start=clock();
  			HeapSort(L);
  			finish=clock();
  			break;
  	default: flag=0;
  			printf("Press any key to exit!\n");
  			getch();
  	
  	
  }
  printf("\n");
  OutputSqlist(L);
  duration=(double)(finish-start);
  printf("\nThe Sort Spend :%lf Seconds\n",duration);
  printf("\n这个排序共比较%4d次，共移动元素%4d次",count1,count2);
  	
	 
	}	
	return 1;
}