sort_merge.cpp

来自「自己编写的排序算法的代码」· C++ 代码 · 共 86 行

#include <fstream.h>
#include "data.h"

//二路归并

void Merge(int a[],int low,int mid,int high)
{
	int al,ah,i,j,k;
	al=mid-low+1;
	ah=high-mid;
	int *arrayl,*arrayh;
	//以下在内存中申请两个工作区
	arrayl=new int[al];
	if(!arrayl)
	{
		cout<<"内存空间申请失败"<<endl;
		return;
	}
	arrayh=new int[ah];
	if(!arrayh)
	{
		cout<<"内存空间申请失败"<<endl;
		return;
	}
	for(i=0;i<al;i++)
		arrayl[i]=a[low+i];
	for(j=0;j<ah;j++)	
		arrayh[j]=a[mid+1+j];
	i=0;
	j=0;
	k=low;
	while(i<al&&j<ah)             //合并
	{
		if(arrayl[i]<arrayh[j])
		{
			a[k]=arrayl[i];
			i++;
		}
		else
		{
			a[k]=arrayh[j];
			j++;
		}
		k++;
	}
	while(i<al)                   //把剩下的一个数组中，余下的元素复制到原数组中
	{
		a[k]=arrayl[i];
		i++;
		k++;
	}
	while(j<ah)
	{
		a[k]=arrayh[j];
		j++;
		k++;
	}
	delete arrayl;
	delete arrayh;
}


//归并排序
void Merge_S(int a[],int low,int high)
{
	int mid;
	if(low<high)
	{
		mid=(low+high)/2;
		Merge_S(a,low,mid);
        Merge_S(a,mid+1,high);
        Merge(a,low,mid,high);
	}
}
////////////////////////
void Merge_Sort(int a[])
{
	int l,h;
	l=0;
	h=number-1;
    Merge_S(a,l,h);
}