#include "stdafx.h"
#include <stdio.h>
#include <ctype.h>
#include <iostream.h>

void bubble(int a[], int size)
{	
	cout<<"?°?Y??Dò:"<<endl;
	for(int i = 1; i < size; i++)// loop size-1 times
		{	for(int j = 0; j < size - i; j++)
			if(a[j] > a[j+1])
			{	int temp = a[j];
				a[j] = a[j+1];
				a[j+1] = temp;
			}
			for(int k = 0; k < size; k++)
				cout<<a[k];
			cout<<endl;
		}
}
		
void insert_sort(int a[], int size)
{
	cout<<"2?è???Dò:"<<endl;
	int inserter,i = 0,index;
	for(i = 1; i < size; i++)
	{
		inserter = a[i];
		index = i - 1;
		while(index >= 0 && inserter < a[index])//?-?·size-1′?
		{	a[index+1] = a[index];
			index--;
		}
		a[index+1] = inserter;//2?è?
		for(int k = 0; k < size; k++)
		{
			cout<<a[k];
			//if(k==i)
			//	cout<<"!";//?′??Dòμ?·??a??
		}
		cout<<endl;
	}
}

void quicksort(int a[], int low, int high)//?ì?ù??Dò
{	
	int i,j,key,temp;
	for(i = 0; i <= high; i++)
		cout<<a[i];
	cout<<endl;
	if(low < high)
	{
		key = a[low];
		i = low;
		j = high;
		while(i < j)
		{
			for( i = i + 1; i < high; i++)
				if( a[i] > key)
					break;
			for( j = j; j > low; j--)
				if( a[j] < key)
					break;
			if(i < j)
			{	temp = a[i];
				a[i] = a[j];
				a[j] = temp;
			}
		}
		temp = a[low];
		a[low] = a[j];
		a[j] = temp;
		//cout<<"j:"<<j<<"   i:"<<i<<endl;
		quicksort(a,low,j-1);
		quicksort(a,i,high);
	}
}	

void shellsort(int a[], int low, int high)
{	cout<<"?￡????Dò:"<<endl;
	int size = low + high + 1;
	int d = size;
	while(d > 1)
	{	d = (d + 1)/2;//dè?5￡?3￡?2￡?1
		//cout<<"d:"<<d<<endl;
		for(int i = low; i < size - d; i++)
			if(a[i] > a[i+d])
			{	int temp = a[i];
				a[i] = a[i+d];
				a[i+d] = temp;
			}
		for (int k = 0; k < size; k++)
			cout<<a[k];
		cout<<endl;
	}
}

void print(int s[],int size)
{		cout<<"Print:"<<endl;
		for(int j = 0; j < size; j++)
			cout<<s[j];
		cout<<endl;
}
void select(int s[], int size)
{
	int low = 0;
	int high = size - 1;
	int t;
	cout<<"??????Dò·?·¨￡o"<<endl;
	cout<<"1￡o?°?Y??Dò"<<endl;
	cout<<"2￡o2?è???Dò"<<endl;
	cout<<"3￡o?ì?ù??Dò"<<endl;
	cout<<"4￡o?￡????Dò"<<endl;
	cout<<"0:í?3?"<<endl;
	cin>>t;
	switch(t)
	{	case 1: bubble(s,size); print(s,size);break;
		case 2: insert_sort(s,size); print(s,size);break;
		case 3: quicksort(s,low,high);print(s,size);break;
		case 4: shellsort(s,low,high);print(s,size);break;
		case 0: return;
		default : cout<<"ê?è?′í?ó"<<endl;
	}
	select(s,size);
}

int main(int argc, char* argv[])
{
	int s[] = {2,4,6,5,1,3,9,7,0,8};
	int size = sizeof(s)/sizeof(int);
	select(s,size);
	return 0;
}