#include<stdio.h>
#include<conio.h>
#include<string.h>
#include<time.h>
#include<stdlib.h>


void displaysorts(int src[], int des[], int n);
void outdata(int src[],int n);
void outruntime(int runtime);
int  choiceYN(void);

void bubblesort(int src[],int n);
void bubblesort2(int src[],int n);
void insertsort(int src[],int n);
void shellsort(int src[],int n);
void heapsort(int src[],int m);
void sift(int src[],int,int);
void quicksort(int src[],int low,int high);
void mergesort(int src[],int n);
void mergpass(int src[],int des[],int,int);
void merge(int src[],int des[],int i,int y,int z);
void selectsort(int src[],int n);
void radixsort(int src[],int n);

int  bDisplayResult=0;		/* 是否顯示排序后數(shù)據(jù) */

void main()
{
	int i,n;
	int *bak,*des;

	i=clock();
	srand(i);
	printf("請(qǐng)輸入實(shí)驗(yàn)數(shù)據(jù)個(gè)數(shù)，典型數(shù)據(jù)如10、100、...、1000000:");
	scanf("%d",&n);
	/*獲得隨機(jī)數(shù)據(jù)*/
	bak=(int*)malloc(sizeof(int)*n);
	des=(int*)malloc(sizeof(int)*(n+1));		/*某些排序需前加一空位，以提高效率*/
	for(i=0;i<n;i++)
		bak[i]=::rand();

	printf("是否顯示排序后結(jié)果:[Y/N]");
	bDisplayResult=choiceYN();

	printf("=============無序數(shù)據(jù)排序======================\n");
	outdata(bak,n);
	displaysorts(bak, des, n);
	printf("===============================================\n");

	printf("是否進(jìn)行正序各反序的數(shù)據(jù)實(shí)驗(yàn)？[Y/N]:");
	i=choiceYN();
	if ( i )
	{
		memcpy(bak, des, sizeof(int)*n);
		printf("=============正序數(shù)據(jù)排序======================\n");
		outdata(bak,n);
		displaysorts(bak, des, n);
		printf("===============================================\n");

		for ( i=n-1; i>=0; i--)
			bak[n-1-i]=des[i];
		printf("=============反序數(shù)據(jù)排序======================\n");
		outdata(bak,n);
		displaysorts(bak, des, n);
		printf("===============================================\n");

	}

	free(bak);
	free(des);
	printf("按任一鍵結(jié)束...");
	getch();
}

int choiceYN()
{
	int ret;
	for ( char ch=0; ch=getch(); )
	{
		if( ch=='y'||ch=='Y' )
		{
			ret=1;
			printf("Y\n");
			break;
		}
		else if ( ch=='n'||ch=='N' )
		{
			ret=0;
			printf("N\n");
			break;
		}
	}
	return ret;
}

void displaysorts(int src[], int des[], int n)
{
	int begin,end;

	memcpy(des, src, sizeof(int)*n);
	printf("---- bubble sort ----\n");
	begin=clock();
	bubblesort(des,n);
	end=clock();
	outdata(des,n);
	outruntime(end-begin);

	memcpy(des, src, sizeof(int)*n);
	printf("---- bubble sort 2 ----\n");
	begin=clock();
	bubblesort2(des,n);
	end=clock();
	outdata(des,n);
	outruntime(end-begin);

	memcpy(des, src, sizeof(int)*n);
	printf("---- quick sort ----\n");
	begin=clock();
	quicksort(des,0,n-1);
	end=clock();
	outdata(des,n);
	outruntime(end-begin);

	memcpy(des, src, sizeof(int)*n);
	printf("---- select sort ----\n");
	begin=clock();
	selectsort(des,n);
	end=clock();
	outdata(des,n);
	outruntime(end-begin);

	memcpy(des, src, sizeof(int)*n);
	printf("---- HEAP SORT ---- \n");
	begin=clock();
	heapsort(des,n);
	end=clock();
	outdata(des,n);
	outruntime(end-begin);

	memcpy(&des[1], src, sizeof(int)*n);
	printf("---- INSERT SORT ----\n");
	begin=clock();
	insertsort(des,n);	/*在此在數(shù)組前留一空位*/
	end=clock();
	outdata(&des[1],n);
	outruntime(end-begin);

	memcpy(des, src, sizeof(int)*n);
	printf("---- SHELL SORT ----\n");
	begin=clock();
	shellsort(des,n);
	end=clock();
	outdata(des,n);
	outruntime(end-begin);

	memcpy(des, src, sizeof(int)*n);
	printf("---- MERGE SORT ----\n");
	begin=clock();
	mergesort(des, n);
	end=clock();
	outdata(des,n);
	outruntime(end-begin);

	memcpy(des, src, sizeof(int)*n);
	printf("---- radix sort ----\n");
	begin=clock();
	radixsort(des,n);
	end=clock();
	outdata(des,n);
	outruntime(end-begin);
}


void outdata(int src[],int n)
{
	int i;
	if( bDisplayResult )
	{
		for(i=0;i<n;i++)
			printf("%-7d", src[i]);
		printf("\n");
	}
}


void outruntime(int runtime)
{
	printf("%.4f秒",(long double) runtime/CLOCKS_PER_SEC);
	printf("\n");
}

/*============================================================================*/
/*冒泡排序(下沉)*/
void bubblesort(int src[],int n)
{
	int i,j,x;
	int bexchange;
	for(i=n-1;i;i--)
	{
		bexchange=0;
		for(j=0;j<i;j++)
		{
			if(src[j]>src[j+1])
			{
				x=src[j+1];
				src[j+1]=src[j];
				src[j]=x;
				bexchange=1;
			}
		}

		if( !bexchange )
			return;
	}
}

/*冒泡排序改進(jìn)，先下沉一次，再上浮一次*/
void bubblesort2(int src[],int n)
{
	int i,j,k;
	int tmp;
	int bexchange;
	for(i=0,j=n-1; i<j;)
	{
		bexchange=0;
		for(k=i;k<j;k++)	/*下沉一次*/
		{
			if(src[k]>src[k+1])
			{
				tmp=src[k+1];
				src[k+1]=src[k];
				src[k]=tmp;
				bexchange=1;
			}
		}
		j--;

		if( bexchange )
		{
			bexchange=0;
			/*for(k=j-1; k>i; k--)	上浮一次*/
			for(k=j; k>i; k--)		/*修正*/
				if(src[k+1]<src[k])
				{
					tmp=src[k+1];
					src[k+1]=src[k];
					src[k]=tmp;
					bexchange=1;
				}
		}
		i++;

		if ( !bexchange )
			return;
	}
}

/*快速排序*/
void quicksort(int src[],int low,int high)
{
	int i,j;
	int tmp;
	if(low<high)
	{
		i=low;
		j=high;
		tmp=src[low];	/*選第一個(gè)值*/
		while(i<j)
		{
			while(i<j && src[j]>tmp)
				j--;
			if(i<j)
				src[i++]=src[j];
			while(i<j&&src[i]<=tmp)
				i++;
			if(i<j)
				src[j--]=src[i];
		}
		src[i]=tmp;

		quicksort(src,low,i-1);
		quicksort(src,i+1,high);
	}
}


/*選擇排序*/
void selectsort(int src[],int n)
{
	int i,j,k,tmp;
	for(i=0;i<n;i++)
	{
		k=i;
		for(j=i+1;j<n;j++)
			if(src[j]<src[k])
				k=j;
		if(k!=i)
		{
			tmp=src[i];
			src[i]=src[k];
			src[k]=tmp;
		}
	}
}


/*堆排序*/
void heapsort(int src[],int n)
{
	int k, des;
	long tmp;

	for(k=n/2-1;k>=0;k--)		/*建堆*/
		sift(src, n, k);

	for(des=n-1;des>0;des--)	/*排序*/
	{
		tmp=src[0];
		src[0]=src[des];
		src[des]=tmp;
		sift(src,des,0);
	}
}

void sift(int src[],int n,int k)
{
	int i,j;
	int tmp;
	i=k;
	j=2*i+1;
	tmp=src[i];
	while(j<n)
	{
		if((j<n-1)&&(src[j]<src[j+1]))
			j++;
		if(tmp<src[j])
		{
			src[i]=src[j];
			i=j;
			j=2*i+1;
		}
		else
			break;
	}
	src[i]=tmp;
}


/*插入排序*/
void insertsort(int src[],int n)
{
	int i,j;
	int tmp;
	for(i=2;i<=n;i++)
	{
		tmp=src[i];
		src[0]=tmp;
		j=i-1;
		while( tmp<src[j])
		{
			src[j+1]=src[j];
			j--;
		}
		src[j+1]=tmp;
	}
}


/*希爾排序*/
void shellsort(int src[],int n)
{
	int gap,i,j,temp;
	for(gap=n/2;gap>0;gap/=2)
		for(i=gap;i<n;i++)
			for(j=i-gap; (j>=0)&&(src[j]>src[j+gap]); j-=gap)
			{
				temp=src[j];
				src[j]=src[j+gap];
				src[j+gap]=temp;
			}
}

/*基數(shù)排序*/
void radixsort(int src[],int n)
{
	int keysize=5;
	int i,j,k,t;
	int d,e,m=0;
	int *c[10],z[10];

	for (i=0;i<10;i++)
		c[i]=(int*)malloc(sizeof(int)*n);

	for(i=0;i<keysize;i++)
	{
		memset(z,0,sizeof(z));
		for(j=0;j<n;j++)
		{
			k=src[j];
			for (t=0;t<i;t++)
				k=k/10;
			k=k%10;
			*(c[k]+z[k])=src[j];
			z[k]++;
		}

		m=0;
		for(d=0;d<10;d++)
		{
			for(e=0;e<z[d];e++)
			{
				src[m]=*(c[d]+e);
				m++;
			}
		}
	}

	for (i=0;i<10;i++)
		free(c[i]);
}


/*合并排序*/
void mergesort(int src[],int n)
{
	int *des=(int*)malloc(sizeof(int)*n);
	int f,len;
	f=0;
	len=1;
	while(len<n)
	{
		if(f==0)
		{
			f=1;
			mergpass(src,des,n,len);
		}
		else
		{
			f=0;
			mergpass(des,src,n,len);
		}
		len=2*len;
	}
	if(f)
		memcpy(src,des,sizeof(int)*(n));

	free(des);
}

void mergpass(int src[],int des[],int n,int len)
{
	int f_start, s_end;

	f_start=0;
	while(f_start+len<n)
	{
		s_end=f_start+2*len-1;
		if(s_end>=n)	/*最后一段可能不足n*/
			s_end=n-1;
		merge(src,des,f_start,f_start+len-1,s_end);
		f_start=s_end+1;
	}
	if(f_start<n)
		for(; f_start<n; f_start++)
			des[f_start]=src[f_start];
}

void merge(int src[],int des[],int start,int m,int n)
{
	int i,j,k;
	k=i=start;
	j=m+1;
	while(i<=m && j<=n )
	{
		if(src[i]<=src[j])
			des[k++]=src[i++];
		else
			des[k++]=src[j++];
	}
	while(i<=m)
		des[k++]=src[i++];
	while(j<=n)
		des[k++]=src[j++];
}