排序问题中的分治法——归并排序_使用分治法的设计策略设计归并排序程序,并通过如下序列来检验程序是否能正确

归并排序，是创建在归并操作上的一种有效的排序算法。算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。归并排序思路简单，速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列。

基本思想

归并排序是用分治思想，分治模式在每一层递归上有三个步骤：

• 分解（Divide）：将n个元素分成个含n/2个元素的子序列。
• 解决（Conquer）：用合并排序法对两个子序列递归的排序。
• 合并（Combine）：合并两个已排序的子序列已得到排序结果。

【问题】应用归并排序方法对一个记录序列进行升序排列归并排序的分治策略如下如所示

 描述如下：

（1)划分：将待排序序列r1,r2,···,rn划分为两个长度相等的子序列r1,···,rn/2和rn/2+1,···,rn。
（2)求解子问题：分别对这两个子序列进行排序，得到两个有序子序列。
（3)合并：将这两个有序子序列合并成一个有序序列。

【想法】
        归并排序首先执行划分过程，将序列划分为两个子序列，如果子序列的长度为1,则划分结束，否则继续执行划分，结果将具有n个待排序的记录序列划分为n个长度为1的有序子序列；然后进行两两合并，得到[n/2]个长度为2(最后一个有序序列的长度可能是1)的有序子序列，再进行两两合并，得到［n/4]个长度为4的有序序列（最后一个有序序列的长度可能小于4),······直至得到一个长度为n的有序序列。

【算法】

归并排序MergeSort

输入：待排序数组r[n],待排序区间[s,t]

输出：升序序列r[s]～r[t]

1.如果s==t.则待排序区间只有一个记录，算法结束；

2.计算划分中点：m=(s+t)/2；

3.对前半个子序列r[s]～r[m]进行升序排序

4.对后半个子序列r[m+1]～r[t]进行升序排序；

5.合并两个升序序列；

【算法实现】

#include<stdio.h>
 
void Merge(int r[], int c[], int s, int m, int t)
{
	int i = s, j = m + 1, k = s;
	while (i <= m && j <= t)
	{
		if (r[i] <= r[j]) c[k++] = r[i++];    //比较r[i]和r[j]的大小，将较小的放入c[]中
		else c[k++] = r[j++];
	}
	while (i <= m)                            //若第一个子序列没处理完，则进行收尾处理
		c[k++] = r[i++];
	while (j <= t)                            //若第二个子序列没处理完，则进行收尾处理
		c[k++] = r[j++];
}
 
void MergeSort(int r[], int s, int t)         //对序列r[s]～r[t]进行归并排序
{
	int c[100];                               //定义一个临时数组，用来存放排序后的数据
	if (s == t) return;                       //递归的边界条件，只剩一个记录，已经有序
	else
	{
		int m = (s + t) / 2;                  //划分
		MergeSort(r, s, m);                   //对前半个子序列进行排序
		MergeSort(r, m + 1, t);               //对后半个子序列进行排序
		Merge(r, c, s, m, t);                 //合并两个子序列，存放到数组c[]中
		for (int i = s; i <= t; i++)          //将有序数列传回到数组r中
		{
			r[i] = c[i];
		}
	}
}
 
int main()
{
	int r[100];
	int s, t, n;
	printf("共有几个数：");
	scanf("%d", &n);
	printf("输入待排序数组：");
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &r[i]);
	}
	printf("输入待排序区间：");
	scanf("%d %d", &s, &t);
	MergeSort(r, s, t);
	for (int j = 0; j < n; j++)
	{
		printf("%d", r[j]);
	}
	
}

运行结果：

【算法分析】设待排序记录个数为n，则执行一趟合并算法的时间复杂性为O(n)，所以，归并排序算法存在如下递推式：

 

 根据递归算法的时间复杂度计算可得O(nlogn)