归并排序.txt

来自「里面包含vc的经典算法,如动态规划,分治,回溯,贪心算法等」· 文本 代码 · 共 53 行

#include <iostream.h>

int  A[100] ;

void MergeR(int B[],int L1,int R1,int L2 ,int R2 ,int b)
{
	if(L1>R1&&L2>R2) return ;
	if(L1<=R1&&L2<=R2) 
	{
		if(A[L1]<A[L2]) B[b++] = A[L1++] ;
		else B[b++] = A[L2++] ;
	}
	if(L1<=R1)  B[b++] = A[L1++] ;
	if(L2<=R2)  B[b++] = A[L2++] ;
	MergeR(B,L1,R1,L2,R2,b) ;
}

void Merge(int low, int mid , int high)
{
	int k = 0;
	int *B = new int [high-low+1] ;
	MergeR(B,low,mid,mid+1,high,k) ;
	for( k = 0 ; k < high - low +1 ; k ++)
		A[low+k] = B[k] ;
	delete []B;
}



void MergeSort(int low ,int high)
{
	int mid = (low+high )/2;
	if(low < high)
	{
    	MergeSort(low,mid);
		MergeSort(mid+1,high);
		Merge(low,mid,high);
	}
}

int main()
{
	int count,i ;
	cin>>count ;
	for(i = 0  ; i < count ; i ++)
       cin>>A[i] ;
	MergeSort(0 , count-1); 
	for(i = 0 ; i < count ; i ++)
		cout<<A[i]<<" ";
	cout<<endl;
	return 1;
}