分治法设计思想。
分治者，分而治之也。分治法（divide and conquer method）将一个难以解决的大问题划分成为一个规模较小的子问题，分别求解各个子问题，再合并子问题的解。一般来说分治法求解过程分为以下三个阶段。
（1）划分：把规模为n的问题划分为k个规模较小的子问题。
（2）求解子问题：各子问题的解法与原问题的解法是相同的，可以用递归的方法求解各子问题，有时递归处理也可以用循环来实现。
（3）合并：把各子问题的解合并起来，合并的代价因情况不同有很大的差异，分治算法的效率很大程度上依赖于合并的实现。
排序问题中的分治法：
归并排序：
O(nlogn) 。
void MergeSort(int r[ ], int s, int t) //进行归并排序。
{
int m,r1[1000];
if(s==t) return;
else {
m=(s+t)/2;
Mergesort(r, s, m); //归并排序前半个子序列
Mergesort(r, m+1, t); //归并排序后半个子序列
Merge(r, r1, s, m, t); //合并两个已排序的子序列
}
for(int i=s;i<=t;i++)
r[i]=r1[i];
}
void Merge(int r[ ], int r1[ ], int s, int m, int t)//合并子序列。
{
i=s; j=m+1; k=s;
while (i<=m && j<=t)
{
if (r[i]<=r[j]) r1[k++]=r[i++]; //取r[i]和r[j]中较小者放入r1[k]
else r1[k++]=r[j++];
}
if (i<=m) while (i<=m)
//若第一个子序列没处理完，则进行收尾处理
r1[k++]=r[i++];
else while (j<=t)
//若第二个子序列没处理完，则进行收尾处理
r1[k++]=r[j++];
}
快速排序：
【思路】
（1）划分：选定一个记录作为轴值，以轴值为基准将整个序列划分为两个子序列，轴值的位置i在划分的过程中确定，并且前一个为子序列中的记录小于或者等于轴值； 后一个子序列中的记录均大于或者等于轴值。
（2）求解子问题，分别对划分后的子问题进行递归处理。
（3）把子序列就地排序，并不需要任何的合并就得到一个排序序列。
【例题】：
初始序列为 23 13 35 6 19 50 28
【想法】：首先对待排序列记录进行划分，划分的轴值应该遵循平衡子问题的原则，使划分后的两个子序列的长度尽量相等，这是决定快速排序算法时间性能的关键。轴值的选择有很多种，我们可以随机选出一个记录作为轴值，从而期望划分是较平衡的。
上述例题我们以第一数为轴值，划分轴值左侧的都小于轴的值，轴值右侧都大于轴值。
a、初始键值序列 23 13 35 6 19 50 28 i指示初值23 j指示最右侧数字。
b、从右侧扫描，j不断移动找到比23小的数字，当j移动到19时，进行比较发现19在23的右侧，但是却是小于23，于是我们把19 和23 的位置进行交换。
c、交换后的序列如下，同时指针i++
19 13 35 6 23 50 28
d、左侧进行扫描直到 i指向的数字大于23 ，扫描到35 ；35 和23 进行交换，交换结果如下所示。
19 13 23 6 35 50 28
e、j向左侧移动一位，j由指向35 移动到指向6，同时判断j指向的是否小于23 ，然后进行交换，交换结果如下所示。
19 13 6 23 35 50 28
f、交换后i++，此时i和j同时指向23 ，这样我们第一次划分结束。
{19 13 6 } 23 { 35 50 28 }
以轴值为基准将待排序列划分为两个子序列后，对每一个子序列分别递归进行处理。处理过程如下所示。
键值初始值：23 13 35 6 19 50 28
第一次划分之后：{19 13 6 } 23 { 35 50 28 }
分别进行快速排序：{ 6 13 } 19 23 { 28 } 35 { 50 }
6 { 13 } 19 23 28 35 50
最终结果为：6 13 19 23 28 35 50
【C代码如下所示：】
一次划分函数。
int Partition(int r[ ], int first, int end)
{
i=first; j=end; //初始化
while (i<j)
{
while (i<j && r[i]<= r[j]) j--； //右侧扫描
if (i<j) {
r[i]←→r[j]; //将较小记录交换到前面
i++;
}
while (i<j && r[i]<= r[j]) i++； //左侧扫描
if (i<j) {
r[j]←→r[i]; //将较大记录交换到后面
j--;
}
}
retutn i; // i为轴值记录的最终位置
}
不断的确定轴值。
void QuickSort(int r[ ], int first, int end)
{
if (first<end) {
pivot=Partition(r, first, end);
//问题分解，pivot是轴值在序列中的位置
QuickSort(r, first, pivot-1);
//递归地对左侧子序列进行快速排序
QuickSort(r, pivot+1, end);
//递归地对右侧子序列进行快速排序
}
}
本节完毕，下一节减治法。