算法设计策略----分治法

分治法：求解一个复杂问题可以将其分解成若干子问题，子问题在分解成更小的问题，直到可以直接求解为止。

一个问题能够用分治法求解的要素是：

1. 问题能够按照某种方法分解为若干个规模较小、相互独立且与原问题类型相同的问题；
2. 子问题足够小时可以直接求解；
3. 能够将子问题的解组合成原问题的解。

算法框架：

SolutionType DandC(ProblemType P){
    ProblemType P1,P2,P3,...Pn;
    if(Small(P))    return S(P);    //子问题P足够小，直接求解
    else{
        Divide(P1,P2,P3,...Pn);    //将问题P分解为子问题P1,P2,...Pn
        Return Combine(DandC(P1),DandC(P2),...,DandC(Pk));    //求解子问题，并合并解
    }
}

相关算法：

• 二分搜索
• 归并排序
• 快速排序
• 寻找第k个最小元

寻找第k个最小元：在n个元素的集合中，选出某个元素值大小在集合中处于第k位置的元素。

使用快速排序所采用的划分方法，以主元为标准，将一个表划分为两个子表，子左子表中所有元素均小于或等于主元，右子表中元素均大于或等于主元。设表原长为n，左子表长p, 若k = p，则主元就是第k小元素；若k>p, 则第k小元素在右子表中；若k<p, 则第k小元素在左子表中。