#include<stdio.h>
#define maxsize 20
typedef struct
{
	int r[maxsize+1];
	int length;
}SqList;
void InsertSort(SqList L)
{
	int i,j;
	for(i=2;i<=L.length;i++)
	{
		L.r[0]=L.r[i];
		j=i-1;
		while(L.r[0]<L.r[j])
		{
			L.r[j+1]=L.r[j];
			j--;
		}
		L.r[j+1]=L.r[0];
	}
	printf("\nThe InsertSorted numbers are:");
	for(i=1;i<=L.length;i++) printf("%d  ",L.r[i]);
	printf("\n");
}
void BInsertSort(SqList L)
{
	int i,low,high,m,j;
	for(i=2;i<=L.length;i++)
	{
		L.r[0]=L.r[i];
		low=1;
		high=i-1;
		while(low<=high)
		{
			m=(low+high)/2;
			if(L.r[0]<L.r[m]) high=m-1;
			else low=m+1;
		}
		for(j=i-1;j>=high+1;j--) L.r[j+1]=L.r[j];
		L.r[high+1]=L.r[0];
	}
	printf("\nThe BInsertSorted numbers are:");
	for(i=1;i<=L.length;i++) printf("%d  ",L.r[i]);
	printf("\n");
}
int Partition(SqList *L,int low,int high)
{
	int i=low,j=high,x=L->r[i];
	L->r[0]=L->r[i];
	while(i<j)
	{
		while(i<j&&L->r[j]>=x) j--;
		L->r[i]=L->r[j];
		while(i<j&&L->r[i]<=x)i++;
		L->r[j]=L->r[i];
	}
	L->r[i]=L->r[0];
	return i;
}
void QSort(SqList *L,int low,int high)
{
	int k;
	if(low<high)
	{
		k=Partition(L,low,high);
		QSort(L,low,k-1);
		QSort(L,k+1,high);
	}
}
void QuickSort(SqList L)
{
	int i;
	QSort(&L,1,L.length);
	printf("\nThe QuickSorted numbers are:");
	for(i=1;i<=L.length;i++) printf("%d  ",L.r[i]);
	printf("\n");
}
void SelectSort(SqList L)
{
	int i,j,k;
	for(i=1;i<=L.length;i++)
	{
		k=i;
		for(j=i+1;j<=L.length;j++)
			if(L.r[j]<L.r[k]) k=j;
		j=L.r[i];
		L.r[i]=L.r[k];
		L.r[k]=j;
	}
	printf("\nThe SelectSorted numbers are:");
	for(i=1;i<=L.length;i++) printf("%d  ",L.r[i]);
	printf("\n");
}
void HeapAdjust(SqList *L,int s,int m)
{
	int i;
	L->r[0]=L->r[s];
	for(i=2*s;i<=m;i*=2)
	{
		if(i<m&&L->r[i]<L->r[i+1]) i++;
		if(L->r[i]>L->r[0])
		{
			L->r[s]=L->r[i];
			s=i;
		}
		else break;
	}
	L->r[s]=L->r[0];
}
void HeapSort(SqList L)
{
	int i;
	for(i=L.length/2;i>0;i--) HeapAdjust(&L,i,L.length);
	for(i=L.length;i>1;i--)
	{
		L.r[1]=L.r[1]^L.r[i];
		L.r[i]=L.r[i]^L.r[1];
		L.r[1]=L.r[1]^L.r[i];
		HeapAdjust(&L,1,i-1);
	}
	printf("\nThe HeapSorted numbers are:");
	for(i=1;i<=L.length;i++) printf("%d  ",L.r[i]);
	printf("\n");
}
main()
{
	SqList L;
	int i=0;
	printf("Input the data(0 to exit):");
	do
	{
		scanf("%d",&L.r[++i]);
	}while(L.r[i]);
	L.length=i-1;
	InsertSort(L);
	BInsertSort(L);
	QuickSort(L);
	SelectSort(L);
	HeapSort(L);
	getch();
}