insert(int *a,int n)
{
	int i,j;
	for(i=2;i<=n;i++)
	if(a[i]<a[i-1])
	{	a[0]=a[i];
		a[i]=a[i-1];
		for(j=i-2;a[0]<a[j];j--)
		a[j+1]=a[j];
		a[j+1]=a[0];
	}
}
Binsert(int *a,int n)
{	int i,j;
	int low,high,m;
	for(i=2;i<=n;i++)
	{	a[0]=a[i];
		low=1;
		high=i-1;
		while(low<=high)
		{       m=(low+high)/2;
			if(a[0]<a[m])
			high=m-1;
			else  low=m+1;
		}
		for(j=i-1;j>=high+1;j--)
		a[j+1]=a[j];
		a[high+1]=a[0];
	}
}
shellsort(int *a,int n)
{	int i,j,dk;
	dk=n/2;
	while(dk>0)
	{	for(i=dk+1;i<=n;i++)
		if(a[i]<a[i-dk])
		{	a[0]=a[i];
			for(j=i-dk;j>0&&a[0]<a[j];j=j-dk)
			a[j+dk]=a[j];
			a[j+dk]=a[0];
		}
		 dk=dk/2;
	}
}
quicksort(int *a,int low,int high)
{       int pivokey=a[low];
	a[0]=a[low];
	while(low<high)
	{	while(low<high&&a[high]>=pivokey)
		high--;
		a[low]=a[high];
		while(low<high&&a[low]<=pivokey)
		low++;
		a[high]=a[low];
	}
	a[low]=a[0];
	return low;
}
Qsort(int *a,int low,int high)
{	int pivotloc;
	if(low<high)
	{	pivotloc=quicksort(a,low,high);
		Qsort(a,low,pivotloc-1);
		Qsort(a,pivotloc+1,high);
	}
}
selectsort(int *a,int n)
{	int i,j,t;
	for(i=1;i<=n;i++)
	{
		for(j=i+1;j<=n;j++)
		if(a[i]>a[j])
		{
		t=a[i];
		a[i]=a[j];
		a[j]=t;
		}
	}
}
main()
{       int i,j,n;
	int *r;
	printf("Input the number of n:\n");
	scanf("%d",&n);
	printf("Please input numbers:\n");
	for(i=1;i<=n;i++)
	scanf("%d",&r[i]);
	printf("1--Insersort:\n");
	printf("2--Binsersort:\n");
	printf("3--Shellsort:\n");
	printf("4--Quicksort:\n");
	printf("5--Selectsort:\n");
	for(j=1;j<=5;j++)
	{	printf("Input j:\n");
		scanf("%d",&j);
		if(j==1)
		insert(r,n);
		else if(j==2)
		Binsert(r,n);
		else if(j==3)
		shellsort(r,n);
		else if(j==4)
		Qsort(r,1,n);
		else
		selectsort(r,n);
		for(i=1;i<=n;i++)
		printf("%d\t",r[i]);
		printf("\n");
	}
}