本文共 1918 字，大约阅读时间需要 6 分钟。

分治法概述

1、分治法的设计思想

对于一个规模为 n 的问题，当n的值很小时，问题可以被很容易的解决，则可以将这类问题进行分解，分解为 k 个较小的子问题，这些问题相互独立且与原问题的形式相同，递归地解决这些子问题，并将各个子问题的解合并得到原问题的解，这种算法程序设立叫分治法。

分治法所能解决的问题一般包括一下几个特征 1、该问题的规模缩小到一定程度就可以容易额解决 2、该问题可以分解为若干个规模较小的相似问题 3、利用该问题分解出的子问题的解可以合并为该问题的解 4、该问题所分解出的子问题是相互独立的，即子问题之间不包含公共子问题。

2、分治法的求解过程

1、分解成若干个子问题

2、求解子问题 3、合并子问题

分治法实现的归并排序

这里用的是递归的方法，如果对递归的概念不懂的话，这里有一篇讲解递归的博客

分析： 给定一个无序的数组 （12 3 45 21 9） 从中间开始将数组分割， 分割成每个小数组只有一个元素，单个元素一定是有序的，再从下往上进行合并，即先自上而下的分析，自下而上的求解，这种算法的思想与动态规划的思想有些不同。 合并的过程

#include 
   
    #include 
    
     #include 
     
      //合并两个子数组void Merge(int *arr,int low,int mid,int high){
       assert(arr != NULL);    //新申请一个内存用来存储合并后的数组    int *tmp = (int *)malloc(sizeof(int)*(high-low+1));    assert(tmp != NULL);    int i = low;    int j = mid+1;    int k = 0;    //如果需要合并的两个子数组都还有元素    while(i <= mid && j <= high)    {
       	//将较小的数字放到新数组的前面        if(arr[i] < arr[j])        {
               tmp[k++] = arr[i++];        }        else        {
               tmp[k++] = arr[j++];        }    }    //如果左边的数组中还有元素就将左边的合并到新数组    while(i <= mid)    {
           tmp[k++] = arr[i++];    }    //如果右边的数组中还有元素就将右边的合并到新数组    while(j <= high)    {
           tmp[k++] = arr[j++];    }    int len = k;    //将合并后的数组重新放到原数组中国    for(i = low, k = 0; k < len; k++,i++)    {
           arr[i] = tmp[k];    }    //释放开辟的资源    free(tmp);}//分割函数void MergeSort(int *arr,int low,int high){
   	//如果分割后数组中的元素个数多余1个就继续分割    if(low < high)    {
           int mid = (low+high)/2;        //分割左边的数组        MergeSort(arr,low,mid);        //分割右边的数组        MergeSort(arr,mid+1,high);        //将两个数组合并        Merge(arr,low,mid,high);    }}//打印函数void Show(int *arr,int len){
       int i = 0;    for(i = 0; i < len; i++)    {
           printf("%d ",arr[i]);    }    printf("\n");}int main(){
       int arr[] = {
   3,2,1,4,5,2,3,4,1,};    int len = sizeof(arr)/sizeof(arr[0]);    MergeSort(arr,len);    Show(arr,len);    return 0;}
     
    
   

转载地址：http://ptnwi.baihongyu.com/