分治法排序
在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
分治法所能解决的问题一般具有以下几个特征：
1) 该问题的规模缩小到一定的程度就可以容易地解决
2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。
3) 利用该问题分解出的子问题的解可以合并为该问题的解；
4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。
上述的第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；第二条特征是应用分治法的前提它也是大多数问题可以满足的，此特征反映了递归思想的应用；第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。第四条特征涉及到分治法的效率，如果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。
下面的分治法排序的代码
[php]
#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;
}
[/php]
