您当前的位置:首页 > 计算机 > 编程开发 > 数据结构与算法

分治算法(C语言实现)

时间:02-12来源:作者:点击数:

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

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

对于一个规模为 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 作为待排序区域的上下界。在执行过程中,这两个参数随着区域的划分而不断变化。

方便获取更多学习、工作、生活信息请关注本站微信公众号城东书院 微信服务号城东书院 微信订阅号
推荐内容
相关内容
栏目更新
栏目热门