1[1].1merge.cpp

算法分析与设计实验代码

#include <stdio.h>
//待排序数组
int A[10]={2,6,3,8,7,4,9,0,1,5};
//归并两个子集合
void merge(int low,int mid,int high){
	//辅助数组，存放中间结果
	int B[10];
	int i,j,k,l;
	i=low;
	j=low;
	k=mid+1;
	while(i<=mid && k<=high){
		if(A[i]<A[k]){
			B[j]=A[i];
			i++;
		}
		else{
			B[j]=A[k];
			k++;
		}
		j++;
	}
	if(i>mid){
		for(l=k;l<=high;l++){
			B[j]=A[l];
			j++;
		}
	}
	else{
		for(l=i;l<=mid;l++){
			B[j]=A[l];
			j++;
		}
	}
	//把已排序数组复制到待排序数组
	for(i=low;i<=high;i++){
		A[i]=B[i];
	}
}
//归并分类
void mergesort(int low,int high){
	int mid;
	if(low<high){
		mid=(low+high)/2;
		//分类
		mergesort(low,mid);
		mergesort(mid+1,high);
		//归并两个已经分类的子集合
		merge(low,mid,high);
	}
}
void main(){
	//打印原始数据
	int i;
	printf("原始待排序数据：");
	for(i=0;i<=9;i++){
		printf("%-4d",A[i]);
	}
 	mergesort(0,9);
	//输出结果到屏幕
	printf("\n归并排序之后：");
	for(i=0;i<=9;i++){
		printf("%-4d",A[i]);
	}
	printf("\n");
}