#include
#include
#include?
#include?
#include?
#include?
using?namespace?std;
const?int?Max=1000005;
int?arr[Max]=?{0}b[Max];
long?long?int?bijiao[5]=?{0}jiaohuan[5]=?{0}yidong[5]=?{0};
typedef?struct?{
	long?long?int?num;
	long?long?int?time;
	int?mingci;
}?time1;

int?cmp（const?time1?&aconst?time1?&b）?{
	return?a.time?}

int?cmp1（const?time1?&aconst?time1?&b）?{
	return?a.num?}

void?init（int?num）?{
	int?i;
	if（num>=Max）?{
		cout<<“輸入數字太大！！！結束程序“<		exit（2）;
	}
	srand（（unsigned）?time（NULL））;
	for（i=0;?i		b[i]=arr[i]=rand（）%10000;
	}
	return;
}

void?huanyuan（int?num）?{
	int?i;
	for（i=0;?i		arr[i]=b[i];
	}
}

void?insertSort（int?R[]int?n）?{?//?待排數據存在R[]中默認為整型個數為n
	int?i?j?temp;
	for（i=2;?i<=n;?i++）?{?/*??數組從下標1開始存儲第一個元素有序所以從第二個元素開始處理??*/
		if（R[i]			bijiao[0]++;
			yidong[0]++;
			temp=R[i];???//?將待插入元素暫時存于temp中
			j=i-1;
			while（temp=1）?{?//?下面的循環完成尋找插入位置的功能
				bijiao[0]++;
				yidong[0]++;
				R[j+1]=R[j]??;
				jiaohuan[0]++;
				j--;
			}
		}
		R[j+1]=temp;
		//?找到插入位置后將temp中暫存的待插入元素插入
	}
}

void?shellSort（int?arr[]?int?len）?{
	int?h?=?0i?=?0?j?=?0temp;?//設置步長
	for（h?=?1;?h?	while（h）?{
		h?/=?3;
		yidong[1]+=h/3;
		if（h?		for（i?=?h;?i?=?h;?j-=h）?{
				if（arr[j-h]?				bijiao[1]+=h/3;
				jiaohuan[1]+=h/3;
				yidong[1]+=h/3;
				temp?=?arr[j-h];
				arr[j-h]?=?arr[j];
				arr[j]=?temp;
			}
	}
}

void?SelectSort（int?R[]?int?n?）?{
	int?i??j??k?;
	int??temp;
	for?（i=0;?i<=n-1;?++i）?{
		k=i;
		for?（j=i+1;?j<=n;?++j）??/*這個循環是算法的關鍵，它從無序序列中挑出一個最小的元素*/
			if?（R[k]>R[j]）?{
				yidong[2]++;
				jiaohuan[2]++;
				bijiao[2]++;
				k=j;
			}??//每兩個數比較時總是把小的挑出來，并且將其放入下一輪比較數據中
		/*下面的3句完成最小元素與無序序列第一個元素的交換*/
		jiaohuan[2]++;
		bijiao[2]++;
		yidong[2]+=3;
		temp=R[i];
		R[i]=R[k];
		R[k]=temp;
	}
}

int?partition（int?arr[]?int?low?int?high）?{
	int?key;
	key?=?arr[low];
	while（low		while（low?=?key?）?{
			high--;
			bijiao[3]++;
		}

		if（low			yidong[3]++;
			jiaohuan[3]++;
			arr[low++]?=?arr[high];
			bijiao[3]++;
		}

		while（?low			low++;
			bijiao[3]++;
		}

		if（low			jiaohuan[3]++;
			bijiao[3]++;
			yidong[3]++;
			arr[high--]?=?arr[low];
		}

	}
	arr[low]?=?key;
	return?low;
}
void?quickSort（int?arr[]?int?start?int?end）?{
	int?pos;
	if?（start		bijiao[3]++;
		jiaohuan[3]++;
		pos?=?partition（arr?start?end）;
		quickSort（arrstartpos-1）;
		quickSort（arrpos+1end）;
	}
	return;
}

void?merge（int?src[]?int?des[]?int?low?int?high?int?mid）?{
	int?i?=?low;
	int?k?=?low;
	int?j?=?mid?+?1;
	while?（（?i?<=?mid?）?&&?（?j?<=?high?））?{
		bijiao[4]++;
		if?（src[i]?			des[k+