博客

合并排序算法是用分治策略实现对n个元素进行排序的算法，其基本思想是：将待排序的元素分成大小大致相同的两个子集合，分别对两个子集合进行排序，最终将排好序的子集合合并成要求的排好序列的集合。

算法MergeSort中的递归过程只是将待排序集合一分为二，直至待排序集合只剩下一个元素为止，然后不断合并两个排好序的数组，这需要用到合并函数。将数组a中相邻的两个元素两两配对，比较它们的大小，再用合并算法将他们合并起来。

void MergeSort(int a[],int first,int last){
	int mid=0;
	//设置跳出递归
	if(first == last) 
		return;
	
	if(first<last){
		mid=(first+last)/2;//此时mid=(0+6)/2=3
		MergeSort(a,first,mid);
		MergeSort(a,mid+1,last);
		merge(a,first,mid,last);
	}
} 

void merge(int a[],int left,int mid,int right){
	int left_l=left;
	int left_r=mid;
	int right_l=mid+1;
	int right_r=right;
	int k,i;
	int temp[100]={0};
	for(k=0;left_l<=left_r&&right_l<=right_r;k++){
		//如果左边第一个数比右边第一个数小，则左边第一个数写在temp【】的第一位 
		if(a[left_l]<=a[right_l]){
			temp[k]=a[left_l];
			left_l++;
		}
		//如果右边第一个数比左边第一个数小，则右边第一个数写在temp第一位 
		else{
			temp[k]=a[right_l];
			right_l++;
		}
	}
	//左边序列有剩余，就复制到temp的列尾 
	if(left_l<=left_r){
		for(i=left_l;i<=left_r;i++){
			temp[k++]=a[i];
		}
	}
	//右边序列有剩余，复制到temp的列尾
	if(right_l<=right_r){
		for(i=right_l;i<=right_r;i++)
			temp[k++]=a[i];
	}
	//用temp覆盖a【】
	 for(int i=0;i<right-left+1;i++){
	 	a[left+i]=temp[i];
	 }
}

完整代码

#include<stdio.h>
#include<stdlib.h>
void merge(int a[],int left,int mid,int right){
	int left_l=left;
	int left_r=mid;
	int right_l=mid+1;
	int right_r=right;
	int k,i;
	int temp[100]={0};
	for(k=0;left_l<=left_r&&right_l<=right_r;k++){
		//如果左边第一个数比右边第一个数小，则左边第一个数写在temp【】的第一位 
		if(a[left_l]<=a[right_l]){
			temp[k]=a[left_l];
			left_l++;
		}
		//如果右边第一个数比左边第一个数小，则右边第一个数写在temp第一位 
		else{
			temp[k]=a[right_l];
			right_l++;
		}
	}
	//左边序列有剩余，就复制到temp的列尾 
	if(left_l<=left_r){
		for(i=left_l;i<=left_r;i++){
			temp[k++]=a[i];
		}
	}
	//右边序列有剩余，复制到temp的列尾
	if(right_l<=right_r){
		for(i=right_l;i<=right_r;i++)
			temp[k++]=a[i];
	}
	//用temp覆盖a【】
	 for(int i=0;i<right-left+1;i++){
	 	a[left+i]=temp[i];
	 } 
}
void MergeSort(int a[],int first,int last){
	int mid=0;
	//设置 
	if(first == last) 
		return;
	
	if(first<last){
		mid=(first+last)/2;//此时mid=(0+6)/2=3 
		MergeSort(a,first,mid);{}
		MergeSort(a,mid+1,last);
		merge(a,first,mid,last);
	}
} 
int main(){
	int a[100]={0},n;
	printf("请输入需要排序的数字个数：");
   	scanf("%d",&n);
	printf("请输入需要排序的数："); 
	for(int i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	MergeSort(a,0,n-1);
	for(int i=0;i<n;i++){
		printf("%d ",a[i]);
	}
	return 0;
}