// paixu.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
void bubble_sort(int *x, int n);
void shell_sort(int *x, int n);
void select_sort(int *x, int n);
void insert_sort(int *x, int n);
void heap_sort(int *x, int n);
void quick_sort(int *x, int low, int high);

int _tmain(int argc, _TCHAR* argv[])
{
	int buf[12] = {4,6,8,5,9,7,3,2,1,0,11,12};
	int *ptr;
	ptr = buf;
	int i;

	//bubble_sort(ptr, 12);
	//shell_sort(ptr, 12);
	//select_sort(ptr, 12);
	insert_sort(ptr, 12);
	//heap_sort(ptr, 12);
	//quick_sort(ptr,0,11);

	for(i=0;i<12;i++)
	{
		printf("%d\t",*(buf+i));
	}
	return 0;
}

void bubble_sort(int*x , int n)
{
	int i,j,h,k;
	for(i=n-1;i>0;i = h)
	{
		for(j=0,h=0;j<i;j++)
		{
			if(*(x+j)>*(x+j+1))
			{
				k = *(x+j);
				*(x+j) = *(x+j+1);
				*(x+j+1) = k;
				h = j;
			}
		}
	}
	return;
}

void shell_sort(int* x, int n)
{
	int i,j,k,d;
	for(d=n/2;d>0;d=d/2)
	{
		for(i=d;i<n;i++)
		{
			k = *(x+i);
			for(j=i-d;(j>=0&&k<*(x+j));j=j-d)
			{
				*(x+j+d) = *(x+j);
			}
			*(x+j+d) = k;
		}
	}
	return;
}

void quick_sort(int *x, int low, int high)
{
	int i, j, t;
	if(low<high)
	{
		i = low;
		j = high;
		t = *(x+low);
		while(i<j)
		{
			while(i<j&&*(x+j)>t) j--;

			if(i<j)
			{
				*(x+i) = *(x+j);
				i++;
			}

			while(i<j&&*(x+i)<=t) i++;

			if(i<j)
			{
				*(x+j) = *(x+i);
				j--;
			}
		}
		*(x+i) = t;
		quick_sort(x,low,i-1);
		quick_sort(x,i+1,high);
	}
	return;
}

void sift(int* x, int n, int s)
{
	int i, j, t;
	
	i = s;
	t = *(x+i);
	j = 2*i+1;

	while(j<n)
	{
		if(j<n-1&&*(x+j)<*(x+j+1)) j++;

		if(t<*(x+j))
		{
			*(x+i) = *(x+j);
			i = j;
			j = 2*i+1;
		}
		else
		{
			break;
		}
	}
	*(x+i) = t;
}

void heap_sort(int *x, int n)
{
	int i,j,k;

	for(i=n/2-1;i>=0;i--)
	{
		sift(x,n,i);
	}

	for(j=n-1;j>0;j--)
	{
		k = *x;
		*x = *(x+j);
		*(x+j) = k;
		sift(x,j,0);
	}
	return;
}

void select_sort(int *x, int n)
{
	int i,j,min;
	for(i=0;i<n-1;i++)
	{
		min =i;
		for(j=i+1;j<n;j++)
		{
			if(*(x+j)<*(x+min))
			{
				min = j;
			}
		}

		if(min!=i)
		{
			j =	*(x+i);
			*(x+i) = *(x+min);
			*(x+min) = j;
		}
	}
	return;
}

void insert_sort(int *x, int n)
{
	int i,j,t;
	for(i=1;i<n;i++)
	{
		t = *(x+i);
		for(j=i-1;j>=0&&t<*(x+j);j--)
		{
			*(x+j+1) = *(x+j);
		}
		*(x+j+1) =t;
	}
}