C语言——归并排序-创新互联

C语言——归并排序

归并排序用到了分治思想,借助递归的方式对一串数字进行排序,整个过程分为分开和合并两个过程。其实归并排序的思想并不难理解,但是用代码实现它却并不容易,我们要写两个函数去分别实现这个过程,一个函数用来专门分开合并,另一个函数则描述了每一次排序的过程。
我们来看一个例子:

在临夏州等地区,都构建了全面的区域性战略布局,加强发展的系统性、市场前瞻性、产品创新能力,以专注、极致的服务理念,为客户提供成都网站建设、成都网站制作 网站设计制作按需定制开发,公司网站建设,企业网站建设,品牌网站设计,成都全网营销推广,成都外贸网站建设公司,临夏州网站建设费用合理。
a[]={1,3,5,7,2,4,6,8};

对于这个数组,利用归并的思想排序,就是把它分成两个部分,从中间截开,分成两组数:1,3,5,7和2,4,6,8;我们可以发现两组数都是从小到大排序的,我们可以定义两个变量一个指向前一串数的第一个数字,另一个变量指向第二组数的第一个变量,分别比较这两个数,将小的那个放进一个新数组,然后变量往后移,逐个比较,最终就有了一个新数组,这个新数组就是排序好的数组。
但是如果分成两组数之后,两边的数字并不是有序的该怎么办?这时候说明把数组分开一次不够,就要继续再分,如果还不是有序的?再分,直到把它们分为一个一个的数,然后再用归并的思想把它们重新排回原来的数组,整个数组就变得有序了。
在这里可能不太好理解,我们可以看一下下面的图片,或许就好理解很多。
在这里插入图片描述
接下来我们来看代码,首先我们来看第一个函数,第一个函数的作用就是把数组从中间切开再合并。

void merge_sort(int a[],int left,int right){if(leftint mid = (left + right) / 2;//从中间截开
		merge_sort(a,left, mid);//把左边沿中间截开
		merge_sort(a, mid + 1, right);//把右边沿中间截开
		merge(a, left, right, mid);//合并
	}
}

接下来这个函数是合并的过程。

void merge(int a[],int left,int right,int mid) {int s[100];//一个新数组用来存储排序好的数组
	int i = left, j = mid + 1;//两个变量分别指向左边和右边两组数的第一个数
	int sor = left;
	while (i<= mid && j<= right) {if (a[i]< a[j]) {//归并的过程
			s[sor++] = a[i++];
		}
		else {	s[sor++] = a[j++];
		}
	}
	while (i<= mid) s[sor++] = a[i++];//当一组数已经全部排进去之后,再将另外一组数的全部数字都排进去
	while (j<= right)  s[sor++] = a[j++];
	sor = left;
	while (sor<= right) {//把排好序的新数组全部放回原数组里
		a[sor] = s[sor];
		sor++;
	}
}

我们在主函数运行一下这个代码。

#includevoid merge_sort(int a[],int left,int right){if(leftint mid = (left + right) / 2;
		merge_sort(a,left, mid);
		merge_sort(a, mid + 1, right);
		merge(a, left, right, mid);
	}
}
void merge(int a[],int left,int right,int mid) {int s[100];
	int i = left, j = mid + 1;
	int sor = left;
	while (i<= mid && j<= right) {if (a[i]< a[j]) {	s[sor++] = a[i++];
		}
		else {	s[sor++] = a[j++];
		}
	}
	while (i<= mid) s[sor++] = a[i++];
	while (j<= right)  s[sor++] = a[j++];
	sor = left;
	while (sor<= right) {a[sor] = s[sor];
		sor++;
	}
}
int main()
{int a[]={3,9,5,4,64,4,5,9,8,9};
 	int i;
 	merge_sort(a, 0, 9);
 	for(i = 0; i< 10; i++)
	{printf("%d ", a[i]);
	}
 	return 0; 
}

运行结果:
在这里插入图片描述

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


文章标题:C语言——归并排序-创新互联
URL分享:http://pwwzsj.com/article/dhceic.html