#include<iostream.h>
#define MaxSize 10  //一個用作示例的順序表的最大長度

typedef struct RecordType //記錄類型
{ 
	int key;  //關鍵字項

}SqList[MaxSize]; //順序表類型 

void InsertSort(SqList r,int n)  
//直接插入排序,排序元素r[1]-r[n]//
{
	int i,j;
	for(i=2;i<=n;i++)
	{
		r[0]=r[i];  //r[0]為監視哨
		j=i-1;

		while(r[0].key < r[j].key)  //進行元素移動，以便騰出一個位置插入r[i]
		{
			r[j+1]=r[j]; //元素后移
			j--;  
		}
		r[j+1]=r[0];  //在j+1位置處插入r[0]
	}
}

void  BubbleSort(SqList r,int n) 
//起泡排序（冒泡排序）,n->順序表長度//
{
	int i,j;
	RecordType w;

	for(i=1;i<=n-1;i++)
	{
		for(j=n;j>=i+1;j--)
		{
			if(r[j].key < r[j-1].key)  //比較,r[j]與r[j-1]進行交換
			{
				w=r[j];
				r[j]=r[j-1];
				r[j-1]=w;
			}
		}
	}

}

void SelectSort(SqList r,int n)  
//選擇排序//
{
	int i,j,k;
	RecordType temp;

	for(i=1;i<=n-1;i++)
	{
		k=i;
		for(j=i+1;j<=n;j++)
		{
			if(r[j].key < r[k].key) { k=j; } //用k指出每趟在無序區段的最小元素//

			temp=r[i];  //將r[k]與r[i]交換//
			r[i]=r[k];
			r[k]=temp;
		}
	}
}


void ShowSort(SqList r,int n)  //顯示排序結果//
{
	for(int i=1;i<=n;i++)
	{
		cout<<r[i].key<<" ";
	}
	
}


			

void main()
{
	SqList r;
	int n;
	
	bool f;
	f=true;
while(f)
{

	cout<<"請輸入順序表的長度:";
	cin>>n;
	
    cout<<"請輸入順序表的元素:";
	for(int i=1;i<=n;i++)
	{ cin>>r[i].key; }
	cout<<endl;

	cout<<"用<起泡排序>進行排序得到:"<<endl;
	BubbleSort(r,n);
    ShowSort(r,n);
	cout<<endl<<endl;
    
	cout<<"用<插入排序>進行排序得到:"<<endl;
	InsertSort(r,n);
	ShowSort(r,n);
	cout<<endl<<endl;

	cout<<"用<選擇排序>進行排序得到:"<<endl;
	SelectSort(r,n);
	ShowSort(r,n);

	cout<<endl<<endl;

cout<<"要繼續請輸入Y或y，退出按其它鍵:";
char c;
cin>>c;
if(c=='Y' || c=='y') { f=true; }
else { f=false; }
   
cout<<endl;

}

}