归并分类与快速分类平均时间之比较

用C/C++语言编程实现归并分类算法6.3 和快速分类算法6.6。对于快速分类，SPLIT中的划分元素采用三者A(low)，A(high)，A((low+high)/2)中其值居中者。 （2）随机产生20组数据（比如n=5000i，1≤i≤20）。数据均属于范围（0，105）内的整数。对于同一组数据，运行快速分类和归并分类算法，并记录各自的运行时间（以毫秒为单位）。 （3）根据实验数据及其结果来比较快速分类和归并分类算法的平均时间，并得出结论。

#include
#include
#include
#include
using namespace std;
int mergesort（int* Aint amountint lowint high）;
int MERGE（int* Aint amountint lowint midint high）;
int quicksort（int* Aint lowint high）;
int SPLIT（int* Aint lowint high）;
int main（）
{
	int *array1[20]*array2[20]ij;
	//设置array1、array2存放所有组数据的首地址
	//若是用一个数组，第一次排序完毕，第二次排序所需时间一定减少（因为比较后不用互换节省时间），故设置了两个相同的数组，更能比较出谁快谁慢
	srand（（unsigned）time（NULL））;
	for（i=0;i<20;i++）{
		int *A=new int [5000*（i+1）];
		int *B=new int [5000*（i+1）];
		//数组A与数组B存放每一组的数据，由于各组数据元素个数不相同，故设为动态数组
		//数组A与数组B的数据相同
		for（j=0;j<5000*（i+1）;j++）{
			A[j]=rand（）%100000;//是用随机数赋值
			B[j]=A[j];
		}
		//将每组数据首地址赋给array
		array1[i]=A;
		array2[i]=B;
	}

	//实行算法mergesort
	double TimeStart1=GetTickCount（）;//记录排序开始时间
	for（i=0;i<20;i++）
		mergesort（array1[i]5000*（i+1）05000*（i+1）-1）;
	double TimeEnd1=GetTickCount（）;//记录排序结束时间
	double TimeUsed1=TimeEnd1-TimeStart1;//计算出排序所需时间
	cout<<“算法mergesort排序耗时“<
	//实行算法quicksort
	double TimeStart2=GetTickCount（）;//记录排序开始时间
	for（i=0;i<20;i++）
		quicksort（array2[i]05000*（i+1）-1）;
	double TimeEnd2=GetTickCount（）;//记录排序结束时间
	double TimeUsed2=TimeEnd2-TimeStart2;//计算出排序所需时间
	cout<<“算法quicksort排序耗时“<
	//比较两种算法所需时间
	if（TimeUsed1==TimeUsed2）
		cout<<“两种算法一样快！“<	if（TimeUsed1		cout<<“mergesort算法较快！“<	if（TimeUsed1>TimeUsed2）
		cout<<“quicksort算法较快！“<
	for（i=0;i<20;i++）{
		delete arra