- 一、概述
- 1、设计思想
- 2、求解过程
- 二、排序问题
- 1、快速排序(quick sort)
- 2、归并排序(Merge sort)
- 【自底向上的二路归并排序算法】
- 【自顶向下的二路归并排序算法】
- 三、求解查找问题
- 1、查找最大和次大元素
- 2、折半查找
- 3、查一个序列中的第k小元素
- 4、查两个等长有序序列的中位数
- 四、求解组合问题
- 1、求解最大连续子序列和问题
- 2、求解棋盘覆盖问题
- 3、求解循环日程安排问题
- 五、求解大整数乘法和矩阵乘法问题
- 1、求解大整数乘法问题
- 2、求解矩阵乘法问题
2、求解过程对一个规模为n的问题，将其分解为k个规模较小的子问题，这些子问题相互独立且与原问题形式相同，递归解决这些子问题，再合并它们的解得到原问题。
分解（找到基线条件）——求解子问题——合并
divide-and-conquer(P)
{
if |P|≤n0 return adhoc(P);
将P分解为较小的子问题 P1，P2，…，Pk;
for(i=1;i<=k;i++) //循环处理k次
yi=divide-and-conquer(Pi); //递归解决Pi
return merge(y1，y2，…，yk); //合并子问题
}
//k=1，减治法
//k=2，二分法
二、排序问题
1、快速排序(quick sort)
- 【基本思想】
①取基准：任取待排序（n个元素）序列中的一个元素作为基准，一般取端点值
②分区：小于基准值的所有数字组成的子数组+基准值+大于基准值的所有数字组成的子数组
③递归（重复）：对两个子数组重复以上过程直至每个子序列长度为1或0
- 【快速排序的分治策略】
①分解：将原序列a[s…t]分解成两个子序列a[s…i-1]和a[i+1…t]，其中i为划分的基准位置
②求解子问题：若子序列的长度为0或为1，则它是有序的，直接返回；否则递归地求解各个子问题
③合并：由于整个序列存放在数组中a中，排序过程是就地进行的，合并步骤不需要执行任何操作
int Partition(int a[]，int s，int t) //划分算法
{
int i=s，j=t;
int tmp=a[s]; //用序列的第1个记录作为基准
while (i!=j) //从序列两端交替向中间扫描，直至i=j为止
{ while (j>i && a[j]>=tmp)
j--; //从右向左扫描，找第1个关键字小于tmp的a[j]
a[i]=a[j]; //将a[j]前移到a[i]的位置
while (i
void QuickSort(int a[]，int s，int t) //对a[s..t]元素序列进行递增排序
{ if (s int i=Partition(a，s，t);
QuickSort(a，s，i-1); //对左子序列递归排序
QuickSort(a，i+1，t); //对右子序列递归排序
}
}
- 【算法分析】
快速排序算法的平均时间复杂度(最佳情况)是O(n log2n) ，但最糟时其运行时间为O(n²)。
2、归并排序(Merge sort)
- 【基本思想】
①将a[0…n-1]看成是n个长度为1的有序表，将相邻的k（k≥2）个有序子表成对归并，得到n/k个长度为k的有序子表
②将得到的有序子表继续归并，得到 n/k² 个长度为 k² 的有序子表
③重复上述方法直至得到长度为n的有序表
- 【二路归并排序的分治策略】
循环log n(上取整，log为以2为底的对数,下同)次，length依次取1、2、…、log n。每次执行以下步骤：
① 分解：将原序列分解成length长度的若干子序列。
② 求解子问题：将相邻的两个子序列调用Merge算法合并成一个有序子序列。
③ 合并：由于整个序列存放在数组中a中，排序过程是就地进行的，合并步骤不需要执行任何操作。
【自底向上的二路归并排序算法】
自单个元素开始向上成对归并
void MergeSort(int a[]，int n) //二路归并算法
{ int length;
for (length=1;length
- 【算法分析】
对于上述二路归并排序算法，当有n个元素时，需要log n趟归并，每一趟归并，其元素比较次数不超过n-1，元素移动次数都是n，因此归并排序的时间复杂度为O(n log n)
【自顶向下的二路归并排序算法】
自整序列成对分解成单个序列再归并
- 【分治策略】
设归并排序的当前区间是a[low…high]，则递归归并的两个步骤如下：
① 分解：将序列a[low…high]一分为二，即求mid=(low+high)/2；递归地对两个子序列a[low…mid]和a[mid+1…high]进行继续分解。其终结条件是子序列长度为1（因为一个元素的子表一定是有序表）
② 合并：与分解过程相反，将已排序的两个子序列a[low…mid]和a[mid+1…high]归并为一个有序序列a[low…high]
void MergeSort(int a[]，int low，int high) //二路归并算法
{ int mid;
if (low 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或0
- 【算法分析】
设MergeSort(a，0，n-1)算法的执行时间为T(n)，显然Merge(a，0，n/2，n-1)的执行时间为O(n)，所以得到以下递推式：
T(n)=1 当n=1
T(n)=2T(n/2)+O(n) 当n>1
容易推出，T(n)=O(n log n)
三、求解查找问题
1、查找最大和次大元素
2、折半查找
3、查一个序列中的第k小元素
4、查两个等长有序序列的中位数
四、求解组合问题
1、求解最大连续子序列和问题
2、求解棋盘覆盖问题
3、求解循环日程安排问题
五、求解大整数乘法和矩阵乘法问题
1、求解大整数乘法问题
2、求解矩阵乘法问题 
