#include <stdio.h>

void BubbleSort(int a[], int size, int order);
void SelectSort(int a[], int size, int order);
void InsertSort(int a[], int size, int order);
void QuickSort(int a[], int size, int order);


int main()
{
	int a[5]={5,3,4,2,1};
	int i;
	
	//BubbleSort(a,5,1);
	//SelectSort(a,5,1);
	//InsertSort(a,5,1);
	QuickSort(a,5,1);

	for(i=0;i<5;i++)
		printf("%d ",a[i]);

	printf("\n");
	
	return 0;
}


void BubbleSort(int a[], int size, int order) //order为1代表升序,冒泡排序算法
{
	int i, j;
	for(i=0;i<size-1;i++)
	{
		for(j=0;j<size-i-1;j++)
		{
			if((order)?(a[j]>a[j+1]):(a[j]<a[j+1]))
			{
				a[j]=a[j]^a[j+1];
				a[j+1]=a[j]^a[j+1];
				a[j]=a[j]^a[j+1];
			}
		}
	}	
}


void SelectSort(int a[], int size, int order) //order为1代表升序，选择排序算法
{
	int i, j, k;
	for(i=0;i<size-1;i++)
	{
		k=i;
		for(j=i+1;j<size;j++)
		{
			if((order)?(a[k]>a[j]):(a[k]<a[j])) k=j;
		}
		
		if(k!=i)
		{
			a[k]=a[k]^a[i];
			a[i]=a[k]^a[i];
			a[k]=a[k]^a[i];
		}
	}
}


void InsertSort(int a[], int size, int order) //order为1代表升序，插入排序算法
{
	int i, j, k;
	for(i=1;i<size;i++)
	{
		k=a[i];
		j=i-1;
		while(((order)?(a[j]>k):(a[j]<k)) && j>=0)
		{
			a[j+1]=a[j];
			j--;
		}
		a[j+1]=k;
	}
}


void QuickSort(int a[], int size, int order) //order为1代表升序，快速排序算法
{
	int i,j,k;
	if(size<=1) return;

	i=0;
	j=size-1;
	k=a[i];

	while(i!=j)
	{
		while(i!=j && ((order)?(a[j]>=k):(a[j]<=k)))
			j--;
			a[i]=a[j];
		while(i!=j && ((order)?(a[i]<=k):(a[i]>=k)))
			i++;
			a[j]=a[i];
	}

		a[i]=k;
		QuickSort(a,i,1);
		QuickSort(a+i+1,size-i-1,1);

}