凡治众如治寡，分数是也——分治算法

凡治众如治寡，分数是也——分治算法

将一个大规模的问题分解为若干规模较小的相同子问题，分而治之。

使用分治算法的条件

• 原问题可被分解为若干规模较小的相同子问题
• 子问题相互独立
• 子问题的解可以合并为原问题的解

【合并排序】

在数列排序中，如果只有一个数，那么它本身就是有序的；如果只有两个数，那么进行一次比较就可以完成排序。也就是说，数越少，排序越容易。那么，对于一个由大量数据组成的数列，很难一次完成排序，这时可将其分解为小的数列，一直分解到只剩一个数时，本身已有序，再把这些有序的数列合并在一起，执行一个和分解相反的过程，从而完成对整个序列的排序。

合并排序是采用分治策略进行排序的算法，是分治算法的一个典型应用和完美体现。它是一种平衡、简单的二分分治策略。

算法步骤：

• 分解：将待排序的元素分成大小大致相同的两个子序列
• 治理：对两个子序列进行合并排序
• 合并：将排好序的有序子序列进行合并，得到最终的有序序列。

举个栗子：

给定一个数列(42,15,20,6，8,38,50,12)，执行合并排序的过程：

算法设计：

【合并操作】

一个辅助合并函数：Merge(A , low , mid ,high)。

该函数将排好序的两个子序列A[low:mid]和A[mid+1:high]进行合并。其中，low、high代表待合并的两个子序列在数组中的下界和上界，mid代表下界和上界的中间位置

设置3个工作指针i、j、k(整型下标)和一个辅助数组B。

i和j分别指向待排序子序列中当前待比较的元素，k指向辅助数组B中待放置元素的位置。

比较A[i]和A[j]，将较小的赋值给B[k]，相应的指针同时向后移动，如此反复，直到所有的元素都处理完毕。最后把辅助数组B中排好序的元素复制到数组A中。

过程：

第1次比较时，A[i]=4，A[j]=2，将较小的元素2放入数组B中，j++，k ++。

第2次比较时，A[i]=4，A[j]=6，将较小的元素4放入数组B中，i++，k ++。

第3次比较时，A[i]=9，A[j]=6，将较小的元素6放入数组B中，j++，k ++。

第4次比较时，A[i]=9，A[j]=18，将较小的元素9放入数组B中，i ++，k ++。

第5次比较时，A[i]=15，A[j]=18，将较小的元素15放入数组B中，i ++，k ++。

第6次比较时，A[i]=24，A[j]=18，将较小的元素18放入数组B中，j ++，k ++。

第7次比较时，A[i]=24，A[j]=20，将较小的元素20放入数组B中，j ++，k ++。

此时，j >high的后半部分已处理完毕，将前半部分的剩余元素照搬到数组B。

完成合并后，把辅助数组B中的元素复制到原来的数组A中。

【算法代码】

void Merge(int A[],int low, int mid , int high ){
	int *B = new int[high - low + 1]; //开辟一个辅助数组
	int i = low , j = mid + 1 , k = 0;
	while(i <= mid && j <= high){ //按从小到大存放到辅助数组B中
		if(A[i] <= A[j]){
			B[k ++] = A[i ++];
		}
		else{
			B[k ++] = A[j ++];
		}
	}
	while(i <= mid){
		B[k ++] = A[i ++]; //将数组中剩下的元素放置到数组B中
	}
	while(j <= high){
		B[k ++] = A[j ++];
	}
	for(i = low , k = 0 ; i <= high ; i++){
		A[i] = B[k ++];
	}
	delete[] B;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

合并排序

将序列分成两个子序列，然后对子序列进行递归排序，再把两个已排好序的子序列合并成一个有序的序列。

void MergeSort(int A[],int low , int high){
	if(low < high){
		int mid = (low + high) / 2;//取中点
		MergeSort(A , low , mid); //对A[low : mid]中的元素进行合并排序
		MergeSort(A , mid + 1 , high); //对A[mid + 1 : high]中的元素进行合并排序
		Merge(A , low , mid , high);  //合并
	}
}
1
2
3
4
5
6
7
8

【算法分析】

时间复杂度：

分解 → O(1)，递归两个n / 2的子问题 → 2T(n / 2)，合并算法O(n)。

总运行时间：

当n > 1时，递推求解：

递推最终的规模为1，令n = 2 ^ x，则x = log n

∴

空间复杂度：

程序中的变量占用了一些辅助空间，这些辅助空间都是常数阶的，但每调用一个Merge()，都分配一个适当大小的缓冲区，在退出时释放。最多分配的大小为n ，所以空间复杂度为O (n )。递归调用所使用的栈空间等于递归树的深度。

递归树的深度为logn。