heihei12305

归并排序


基本思想：al.....am.....ar -> 两边排序 然后再归并
归并工作量 最好为 n/2,最坏为 n-1 => T(n) = 2* T(n/2)+θ(n* logn)=>由主定理 T(n) = θ(n* logn)

//归并
template<class T>
merge(T *a,int l,int m,int r,T *c)
{
	//[al].....a[m]   ||   a[m+1].....a[r]
	//c[l].........c[m].....c[r]
	int i = l,k = l,j = m+1;
	while(i<=m&&j<=r)
	{
		if(a[i]<a[j])
		{
			c[k++] = a[i++];
		}else{
			c[k++] =a[j++];
		}
	}
	if(i>m)//左侧归并完毕
	{
		while(j<=r)
		{
			c[k+1] = a[j++];
		}
	}else{
		while(i<=m)
		{
			c[k++] = a[i++];
		}
	}
}
template<class T>
void Copy(T *c,int l,int r,T *a)
{
	//c[l].....c[r]   复制到  a[l].....a[r]
	for(int i = l;i<=r;i++)
	{
		a[i] = c[i];
	}
}
//排序算法
template<class T>
MergeSort(T *a,int l,int r,T *c)
{
	if(r<=l)  return ;
	//以下为l<r
	int m = ( l + r )/2;
	//[l,m],[m+1,r]
	MergeSort(a,l,m,c);
	MergeSort(a,m+1,r,c);
	Merge(a,l,m,r,c); //有比较，最坏n-1 ，最好 n/2
	Copy(c,l,r,a); //无比较工作量，仅复制
}
//用法  
int n = 100 0000;
double *a  =new double[n];
for(int i = 0;i<n;i++)
{
	a[i] = Random();
}
double *c  =new double[n];//排序移动方向
MergeSort(a,0,n-1,c);
delete[] c;//清除移动方向
//已排序  a[0]<=...a[n-1]
输出a[i]...
delete[] a;