mergesort.h

八种排序算法

//二路归并
//算法思想:设数组a中存放了n个数据元素,初始时把它们看成是n个长度为1的有序子数组，然后从第一个子数组开始,把相邻的子数组两两合并，
//得到n/2的整数上界个长度为2的新的有序子数组(当n为基数时最后一个新的有序子数组的长度为1);对这些新的有序子数组再两两归并；
//如此重复，直到得到一个长度为n的有序数组为止。多于二路的归并排序方法的二路归并排序方法类同
//算法实现:


//一次二路归并排序算法如下:
void Merge(DataType a[],int n,DataType swap[],int k)
//k为有序子数组的长度，一次二路归并排序后的有序子序列存于数组swap中
{
	int m=0,u1,l2,i,j,u2;
	int l1=0;			//第一个有序子数组下界为0
	while(l1+k<=n-1)
	{
		l2=l1+k;						//计算第二个有序子数组下界
		u1=l2-1;						//计算第一个有序子数组上界
		u2=(l2+k-1<=n-1)?l2+k-1:n-1;	//计算第二个有序字数组上界	

		//两个有序字数组合并
		for(i=l1,j=l2;i<=u1&&j<=u2;m++)
		{
			if(a[i].key<=a[j].key)
			{
				swap[m]=a[i];
				i++;
			}
			else
			{
				swap[m]=a[j];
				j++;
			}
		}

		
		//子数组2已归并完，将子数组1中剩余的元素存放到数组swap中
		while(i<=u1)
		{
			swap[m]=a[i];
			m++;
			i++;
		}

		//子数组1已归并毕,将自数组2中剩余的元素存放到数组swap中
		while(j<=u2)
		{
			swap[m]=a[j];
			m++;
			j++;
		}

		l1=u2+1;
	}

	//将原始数组中只够一组的数据元素顺序存放到数组swap中
	for(i=l1;i<n;i++,m++)
	{
		swap[m]=a[i];
	}

}


//二路归并算法如下:
void MergeSort(DataType a[],int n)
{
	int i,k=1;				//归并长度从1开始
	DataType *swap=new DataType[n];				//申请动态数组空间

	while(k<n)
	{
		Merge(a,n,swap,k);			//调用归并函数Merge(a,n,swap,k)
		for(i=0;i<n;i++)
		{
			a[i]=swap[i];			//将元素从临时数组swap放回数组a中
		}
		k*=2;						//归并长度加倍
	}
	delete [] swap;					//释放动态数组空间
}