#include<iostream.h>
#define key(X) (X)
typedef int ELEM;

inline void swap(ELEM& a, ELEM& b)
{
	ELEM temp = a;
	a = b;
	b = temp;
}

//直接插入排序
void inssort(ELEM* array, int n) { // Insertion Sort
	for (int i=1; i<n; i++)          // Insert i'th record
		for (int j=i; (j>0) && (key(array[j])<key(array[j-1])); j--)
			swap(array[j], array[j-1]);
}

//冒泡排序法
void bubsort(ELEM* array, int n) { // Bubble Sort
	for (int i=0; i<n-1; i++)        // Bubble up i'th record
		for (int j=n-1; j>i; j--)
			if (key(array[j]) < key(array[j-1]))
				swap(array[j], array[j-1]);
}

//選擇排序
void selsort(ELEM* array, int n) { // Selection Sort
	for (int i=0; i<n-1; i++) {      // Select i'th record
		int lowindex = i;              // Remember its index
		for (int j=n-1; j>i; j--)      // Find the least value
			if (key(array[j]) < key(array[lowindex]))
				lowindex = j;              // Put it in place
			　　　swap(array[i], array[lowindex]);
	}
}

void sort(ELEM* array, int n) 
{
	char select;
	int i=1;
	cout<<"Please select one sort method:(b:冒泡排序法；s:選擇排序法；i:插入排序法)"<<endl;
    cin>>select;
	while(i==1)
	{
		switch(select)
		{
		case 'b':
		case 'B':
			bubsort(array, n);
			i=0;
			break;
		case 's':
		case 'S':
			selsort(array, n);
			i=0;
			break;
		case 'i':
		case 'I':
			inssort(array, n);
			i=0;
			break;
		default:
			cout<<"Please select one sort method:
				(b:冒泡排序法；s:選擇排序法；i:插入排序法)"
				<<endl;
			cin>>select;
			break;
		}
	}
}