#include<iostream>
#include<string>
using namespace std;
void DreInsertSort(int a[],int n)
{
	int t,m,k;
	for(int i=1;i<n;i++)
	{
		for(int j=i-1;j>=0;j--)
		{
			if(a[i]>a[j])
				break;
		}
		j++;
		t=a[i];
		for(m=i-1;m>=j;m--)
			a[m+1]=a[m];
		a[j]=t;
		cout<<"第"<<i<<"次：  ";
		for(k=0;k<n;k++)
			cout<<a[k]<<" ";
		cout<<endl;
	}
}

void BubbleSort(int b[],int n)
{
	int t,k;
	for(int i=0;i<n-1;i++)//次數(shù)
	{
		for(int j=0;j<n-i-1;j++)
		{
			if(b[j]>b[j+1])
			{
				t=b[j];
				b[j]=b[j+1];
				b[j+1]=t;
			}
		}
		cout<<"第"<<i+1<<"次：  ";
		for(k=0;k<n;k++)
			cout<<b[k]<<" ";
		cout<<endl;
	}
}

void SelectSort(int c[],int n)
{
	int max,q,k;
	for(int i=0;i<n-1;i++)//找大次數(shù)
	{
		max=c[0];
		q=0;
		for(int j=0;j<n-i-1;j++)
		{
			if(max<c[j+1])
			{
				max=c[j+1];
                q=j+1;
			}

		}
		c[q]=c[n-i-1];
		c[n-i-1]=max;
        cout<<"第"<<i+1<<"次：  ";
		for(k=0;k<n;k++)
			cout<<c[k]<<" ";
		cout<<endl;
	}
}

void ShellSort(int d[],int n)
{
	int l=n/2,t,k;
	while(l>0)
	{
		for(int i=l;i<n;i++)
		{
			int j=i-l;
			while(j>=0&&d[j]>d[j+l])
			{
				t=d[j];
				d[j]=d[j+l];
				d[j+l]=t;
				j=j-l;
			}
		}
		cout<<"l="<<l<<":";
			for(k=0;k<n;k++)
				cout<<d[k]<<" ";
		cout<<endl;
		l=l/2;
	}
	
}


void QuickSort(int e[],int n)
{

}

int main()
{
	int a[100],b[100],c[100],d[100],e[100];
	cout<<"請輸入一個整形數(shù)列，以-1結(jié)尾："<<endl;
	int i=0,j,n;
	while(cin>>n&&n!=-1)
	{
		a[i]=b[i]=c[i]=d[i]=e[i]=n;
		i++;
	}
	cout<<endl<<"直接插入排序過程為："<<endl;
	DreInsertSort(a,i);
	cout<<endl<<"冒泡排序過程為："<<endl;
	BubbleSort(b,i);
	cout<<endl<<"簡單選擇排序過程為："<<endl;
	SelectSort(c,i);
	cout<<endl<<"希爾排序過程為："<<endl;
	ShellSort(d,i);
	cout<<endl<<"快速排序過程為："<<endl;
	QuickSort(e,i);

	






	for(j=0;j<i;j++)
		cout<<e[j]<<" ";
	cout<<endl;
	
	return 0;
}
//9 8 7 6 5 4 3 2 1 0 -1
//49 85 38 72 51 8 19 35 67 100 44 23 1 9 49 -1
//1 2 3 4 5 6 7 8 9 -1