分治算法（C语言实现）

在计算机科学中，分治算法是一种很重要的算法。

字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后可以直接求解子问题，原问题的解即子问题的解的合并。

对于一个规模为 n 的问题，若该问题可以容易地解决（比如说规模 n 较小）则直接解决，否则将其分解为 k 个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。

这种算法设计策略叫作分治算法。

1) C语言分治算法所能解决的问题一般具有以下几个特征。

• 该问题的规模缩小到一定的程度就可以容易地解决。
• 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。（前提）
• 利用该问题分解出的子问题的解可以合并为该问题的解。
• 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

2) C语言分治算法的 3 个步骤如下。

1. 分解：将原问题分解为若干个规模较小、相互独立、与原问题形式相同的子问题。
2. 解决：若子问题规模较小、容易被解决则直接解，否则递归地解各个子问题。
3. 合并：将各个子问题的解合并为原问题的解。

示例

从小到大快速交换排序。C语言编程代码如下：

#include <stdio.h>
#include <stdlib.h>
int partion(int R[ ], int low, int high)   /*对数组R中的R[low]至R[high]间的记录进行一趟快速排序*/

{   int a = R[low];            /*将枢轴记录移至数组的闲置分量*/
    while (low < high)            /*从表的两端交替地向中间扫描*/
    {   while (low<high&& R[high]>a)
            high--;   
        if (low < high)        /*将比枢轴记录小的记录移至低端*/
        {   R[low] = R[high];
            low++;
        }
        while (low < high&& R[low] < a)
            low++;
        if (low < high)        /*将比枢轴记录大的记录移至高端*/
        {   R[high] = R[low];
            high--;
        }
    }
    R[low] = a;        /*将枢轴记录移至正确位置*/
    return low;        /*返回枢轴位置*/
}
void SwapSortB(int R[ ], int b, int c)    /*对数组R中的全部记录按照递增顺序进行快速排序*/
{   int i;
    if (b < c)
    {  i = partion(R, b, c);
        SwapSortB(R, b, i - 1);
        SwapSortB(R, i + 1, c);
    }
}
int main()
{
    int r[11] = { 34546,110, 2, 3, 54, 5, 6, 27, 18, 9, 10 };
    int b = 0;
    int c = 10;
    int i;
    SwapSortB(r, b, c);
    for (i = 0; i < 11; i++)
        printf("%d,", r[i]);
    printf("\n");
}

运行结果：

2,3,5,6,9,10,18,27,54,110,34546,

程序解说：

• 本例中，partion() 函数的功能是对区间 [low，high] 进行一次快速排序的划分。
• 第 4 行代码利用 a 的空间保存枢轴元素的值；
• 第 5~18 行代码利用循环实现一次快速排序的划分，其中第 6 行循环语句的功能是从后往前寻找第一个小于枢轴元素的记录，接着把找到的元素插入枢轴位置；
• 第 12 行是从前向后寻找第一个大于枢轴元素的记录；
• 第 14~16 行代码是把找到的元素插入枢轴位置；
• 第 19 行代码则把枢轴元素插入合适的位置。

快速排序的算法是一个递归函数实例引入一对参数 b 和 c 作为待排序区域的上下界。在执行过程中，这两个参数随着区域的划分而不断变化。