#include?
//#include?
#include?“time.h“
#include?“math.h“
#include?“stdio.h“

using?namespace?std;

#define?max_size?10
#define?N?10000
#define?max?N

int?other[N];

void?swap（int?&aint?&b）
{
	int?temp;
	temp=a;
	a=b;
	b=temp;
}

//插入排序
int?insert_sort（int?A[N+1]）
{?
	clock_t?startend;

	start=clock（）;
????for（int?i=2;i<=N;i++）
	???if（A[i]	???{
		A[0]=A[i];
		for（int?j=i-1;A[0]<=A[j];j--）
			A[j+1]=A[j];
		A[j+1]=A[0];
	???}

/*	for（int?i=2;i<=N+1;i++）
	{
		A[0]=A[i];
		for（int?j=1;j		{
			//改進
????????????if（A[0]<=A[j]）
			{
				A[j+1]=A[j];
			}
			else
			{
				A[j+1]=A[0];
				//break;
			}
????????????????
			if（A[0]<=A[j]）
			{
				for（int?k=i;k>j;k--）
					A[k]=A[k-1];
				break;
			}
		}
		A[j]=A[0];
		
	}*/
	end=clock（）;

	cout<	for（i=1;i<=N;i++）
		printf（“%5d“A[i]）;
		//cout<????//cout<	cout<	return?0;
}


//冒泡排序
bubble_sort（int?A[N+1]）
{
	clock_t?startend;
	//A[0]為哨兵
	start=clock（）;
	for（int?i=1;i		for（int?j=N;j>=i;j--）
		{
			if（A[j]			{
				A[0]=A[j-1];
				A[j-1]=A[j];
????????????????A[j]=A[0];
			}
		}
	end=clock（）;

????cout<	for（i=1;i<=N;i++）
		printf（“%5d“A[i]）;
????cout<	return?0;
}


//快速排序
partition（int?*Aint?iint?j）
{	
	int?privot=A[i];
	while（i	{
		while（A[j]>=privot&&i			j--;
		A[i]=A[j];

		while（privot>=A[i]&&i			i++;
		A[j]=A[i];
	}
	A[i]=privot;
	return?i;
}

void?quick_sort（int?*Aint?lowint?high）
{
????int?pos;
	//clock_t?startend;
	//start=clock（）;
	if（low	{
????????pos=partition（Alowhigh）;
????	quick_sort（Alowpos-1）;
????	quick_sort（Apos+1high）;?
	}
	//end=clock（）;

	//cout<	//for（int?i=1;i<=N;i++）
	//	cout<????//cout<//	return?0;
}


//歸并排序
/*void?merge（int?A[N+1]int?*qint?iint?mint?n）
{
	int?jk;
	for（j=m+1k=i;i<=m&&j<=n;k++）
	{
		if（A[i]<=A[j]）
			q[k]=A[i++];
		else
			q[k]=A[j++];
	}

	while（i<=m）
	????q[k++]=A[i++];
	while（j<=n）
		q[k++]=A[j++];
}

void?m_sort（int?A[N+1]int?*pint?sint?t）
{
	int?mT[N];
	if（s==t）
		p[s]=A[s];
	else
	{
		m=（s+t）/2;
		m_sort（ATsm）;
????????m_sort（ATm+1t）;
		merge（Tpsmt）;
	}
}
*/
void?Merge_Sort（int?*p?int?b?int?e）
{
????if（e-b+1?>?2）?//當數組元素個數大于2時需要繼續向下劃分（遞歸）
????{
????????Merge_Sort（p?b?（e+b）/2）;
????????Merge_Sort（p?（e+b）/2+1?e）;

????????//合并已排序好的兩部分（b（e+b）/2）?和?（（e+b）/2+1e）
????????int?i?=?b?j?=?（e+b）/2+1?k=b;
????????while（i<=（b+e）/2?&&?j<=e）
????????{//比較兩個下標i和j所代表的元素