走刀口

在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

分治法所能解决的问题一般具有以下几个特征：
1) 该问题的规模缩小到一定的程度就可以容易地解决
2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。
3) 利用该问题分解出的子问题的解可以合并为该问题的解；
4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

上述的第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；第二条特征是应用分治法的前提它也是大多数问题可以满足的，此特征反映了递归思想的应用；第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。第四条特征涉及到分治法的效率，如果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。

下面的分治法排序的代码

#include <iostream>
using namespace std;
/**
 * @brief 比较合并
 *
 * @param[in] A 数组指针
 * @param[in] p 数组起始下标
 * @param[in] q 数组分隔下标
 * @param[in] r 数组结束下标
 */
void Merge(int* A, int p, int q, int r)
{
	int n1 = q - p + 1;
	int n2 = r - q;
	int* L = new int[n1 + 1];
	int* R = new int[n2 + 1];
	int i = 0, j = 0;
	for (i = 0; i < n1; ++i)
	{
		L[i] = A[p + i];
	}
	L[n1] = INT_MAX;
	for (j = 0; j < n2; ++j)
	{
		R[j] = A[q + j + 1];
	}
	R[n2] = INT_MAX;
	i = 0; j = 0;
	for (int k = p; k < r + 1; ++k)
	{
		if (L[i] <= R[j])
		{
			A[k] = L[i];
			++i;
		}
		else
		{
			A[k] = R[j];
			++j;
		}
	}
	delete[] L;
	delete[] R;
}
/**
 * @brief 分治
 *
 * @param[in] A 数组指针
 * @param[in] p 数组起始下标
 * @param[in] r 数组结束下标
 */
void MergeSort(int* A, int p, int r)
{
	if (p < r)
	{
		int q = (p + r) / 2;
		MergeSort(A, p, q);
		MergeSort(A, q + 1, r);

		//merge
		Merge(A, p, q, r);
	}
}

int main()
{
	int A[10] = {9,8,7,6,5,4,3,2,1,11};
	MergeSort(A, 0, 9);
	for (int i = 0; i < 10; ++i)
	{
		cout << A[i] << ", ";
	}
	cout << endl;
}