#include?“iostream.h“
#include?“stdio.h“
#include?“stdlib.h“
#include?“time.h“

/*******************************************************************************
	冒泡排序
*******************************************************************************/
long?Bubblesort（long?R[]?long?n）
{
	int?flag=1;						//當(dāng)flag為0則停止排序
	long?BC=0;
	for（long?i=1;i	{								//i表示趟數(shù)最多n-1趟
		flag=0;						//開始時(shí)元素未交換
		for（long?j=n-1;j>=i;j--）
		{
			if（R[j]			{
				long?t=R[j];
				R[j]=R[j-1];
				R[j-1]=t;flag=1;???//交換并標(biāo)記發(fā)生了交換
			}
			BC++;
		}
	}
		return?BC;
}


/*******************************************************************************
	選擇排序
*******************************************************************************/
long?selectsort（long?R[]?long?n）
{
	long?ijm;long?tSC=0;
	for（i=0;i	{
		m=i;
		for（j=i+1;j		{
			SC++;
			if（R[j]			if（m!=i）
			{????
				t=R[i];
				R[i]=R[m];
				R[m]=t;???
			}
		}
	}
	return?SC;
}


/*******************************************************************************
	直接插入排序
*******************************************************************************/
long?insertsort（long?R[]?long?n）
{
	long?IC=0;
	for（long?i=1;i	{
		long?temp=R[i];				//把待排序元素賦給temp
		long?j=i-1;
		while（（j>=0）&&（temp		{
			R[j+1]=R[j];j--;		//順序比較和移動(dòng)
			IC++;
		}
		IC++;
		R[j+1]=temp;
	}
	return?IC;
}

/*******************************************************************************
	希爾排序
*******************************************************************************/
long?ShellSort（long?R[]?int?n）
{
	int?tempSC=0;
	for（int?i?=?n?/?2;?i?>?0;?i?/=?2）					//將所有記錄分成增量為t的子序列
	{
		for（int?j?=?0;?j?			for（int?k?=?j?+?i;?k?				for（int?p?=?j;?p?					if?（R[k]?						temp?=?R[k];
						for（int?q?=?k;?q?>?p;?q?-=?i）{	//插入位置以后的記錄依次后移
							R[q]?=?R[q?-?i];
							SC++;
						}
						R[p]?=?temp;					//插入記錄
						break;
					}
	}
	return?SC;
}

/*******************************************************************************
	快速排序
*******************************************************************************/
long?quicksort（long?R[]?long?left?long?right）
{
	static?long?QC=0;
	long?i=leftj=right;
	long?temp=R[i];
	while（i	{
		while（（R[j]>temp）&&（j>i））
		{
			QC++;
			j=j-1;
		}
		if（j>i）
		{
			R[i]=R[j];
			i=i+1;
			QC++;
		}
		while（（R[i]<=temp）&&（j>i））
		{
			QC++;
			i=i+1;
		}
			if（i			{
				R[j]=R[i];
				j=j-1;
				QC++;
			}
	}
									//二次劃分得到基準(zhǔn)值的正確位置
	R[i]=temp;
	if（left		quicksort（Rlefti-1）;		//遞歸調(diào)用左子區(qū)間
	if（i+1		quicksort（Ri+1right）;		//遞歸調(diào)用右子區(qū)間
	return?QC;
}


/*******************************************************************************
	堆排序
****************************************