C语言实现八种排序 - 归并排序

什么是归并排序？

归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。

将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

步骤如图：

 那我们要如何实现呢？

1. 递归法

代码如下：

// 归并排序
//合并两个有序数组
void Sort(int*a,int left,int mid,int right){
	int*p=(int*)malloc(sizeof(int)*(right-left+1)); //开辟一个大小是right-left+1的空间 
	int p1=left;
	int p2=mid+1;
	int p3=0;
	while(p1<=mid&&p2<=right){
		if(a[p1]<a[p2]){
			p[p3++]=a[p1++];
		}
		else{
			p[p3++]=a[p2++];
		}
	}
	while(p1<=mid)
		p[p3++]=a[p1++];
	while(p2<=right)
		p[p3++]=a[p2++];
	for(int j=0;j<p3;j++){
		a[left+j]=p[j];
	}
	free(p); 
}
void MergeSort(int*a,int left,int right){
	int mid;
	if(left>=right){ //当数组只有一个元素，可以看做有序的 
		return;
	}
	mid=(left+right)/2;
	MergeSort(a,left,mid); //排序左半数组 
	MergeSort(a,mid+1,right); //排序右半数组 
	Sort(a,left,mid,right); //合并两个有序数组 
} 

 这样我们就完成了归并排序的递归版本

2. 非递归版

从图中我们可以看出，最终先合并的是元素个数只剩一个的数组两两合并，那我们使用非递归就可以先实现最后这一步：

//非递归写法 
void MergeSort2(int*a,int n){
	int*tmp = (int*)malloc(sizeof(int)*n);
	int gap=1;//类似于直接先进行递归方式的最后步骤
	while(gap<n){
		for(int i = 0 ; i < n; i += 2*gap){
			int start1=i,end1=i+gap-1; //第一个区间 
			int start2=gap+i,end2=2*gap+i-1; //第二个区间
			int index=i;//每次初始化位置都是第一个区间的起始位置 
			while(start1<=end1&&start2<=end2){
				if(a[start1]<a[start2])
					tmp[index++]=a[start1++];
				else
					tmp[index++]=a[start2++];
			}
			while(start1<=end1)
				tmp[index++]=a[start1++];	
			while(start2<=end2)
				tmp[index++]=a[start2++];  
		}
		memcpy(a,tmp,n*sizeof(int));
		gap *= 2;
	} 
	free(tmp);
} 

 我们将开始数组的大小由1个开始，两两进行归并，最终完成递归的操作，那这样就结束了吗？

我们来看一下每一次归并的数组：

我们这里传入的只是9个元素大小的数组，你怎么给我越界这么多次.

 

 

 那我们应该怎么去修改它，使它无法越界呢？

这里我们需要重新调整我们的区间：

int start1=i,end1=i+gap-1; //第一个区间 
int start2=gap+i,end2=2*gap+i-1; //第二个区间

 这是我们之前定义的区间，由上图我们也可以看到除了start1是个好孩子没有越过界，其他都犯了越界，那我们就应该对它们进行批评改正。

这里我们需要考虑三种情况：

1. 如果end1越界

2. 如果end2越界

3. 如果start2越界

修改操作如下：

            if(end1>=n){
		      end1=n-1;
			} 
			if(start2>=n){
				start2=n;
				end2=n-1;
			}
			if(start2<n&&end2>=n){
				end2=n-1;
			}

 这样我们就可以很好的实现我们的操作