1004.cpp

这是在acm上所做的1003-1004

#include <stdio.h>

#define    MAX 1000000000
#define    N   10000000
unsigned int  L[N],R[N],A[N];

void Merge(unsigned int a[],unsigned int p, unsigned int q,unsigned int r){
//将已排好序的a[p...q]和a[q+1...r]合并

    unsigned int n1,n2,i,j,k;

	n1=q-p+1;
	n2=r-q;
	for(i=1;i<=n1;i++)
		L[i]=a[p+i-1];
	for(j=1;j<=n2;j++)
		R[j]=a[q+j];

	L[n1+1]=MAX;
	R[n2+1]=MAX;

	i=1;j=1;
	for(k=p;k<=r;k++)
		if(L[i]<R[j])
			a[k]=L[i++];
		else
			a[k]=R[j++];

}

void MergeSort(unsigned int a[],unsigned int p,unsigned int r){
//合并排序

	unsigned int q;
	if(p<r){
		q=(p+r)/2;
		MergeSort(a,p,q);
		MergeSort(a,q+1,r);
		Merge(a,p,q,r);

	}

}

int  main(){

	unsigned int i;
	unsigned int n;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d",&A[i]);

	MergeSort(A,1,n);
	for(i=1;i<=n;i++)
		printf("%d ",A[i]);
	putchar('\n');
	return 0;

}