算法

9.3分治法

9.3.1 递归的概念

两个基本要素

边界条件

递归模式

9.3.2分治法的基本思想

设计思想：

将一个难以直接解决的大问题分解成一些规模较小的相同问题以便各个击破。

分而治之。

如果规模为n的问题可分解成k个子问题，1小于k小于等于n，这些子问题互相独立且与原问题相同。分治法产生的子问题往往是原问题的较小规模，递归技术实现

分治算法在每一层递归上都有三个步骤

1分解

2求解

3合并

典型应用

归并排序

归并操作的含义（Merge）

就是将两个或多个有序表合并成一个有序表的过程。若将两个有序表合并成一个有序表则称为二路归并。

如有两个有序表(7,12,15,20)和(4,8,10,17)，归并后得到的有序表为(4,7,8,10,12,15,17,20)。

算法：

1申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列 

2设定两个指针，最初位置分别为两个已经排序序列的起始位置

3比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

4重复步骤3直到某一指针达到序列尾

5将另一序列剩下的所有元素直接复制到合并序列尾

归并排序 

就是利用归并操作把一个无序表排列成一个有序表的过程 

二路归并排序的过程

首先把待排序区间中的每一个元素都看做一个有序表，n个元素有n个

有序表，接着两两归并，即第一个表同第二个表归并，第三个与第四个表归并

若最后只剩下一个表，则直接进入到下一趟归并的过程中

#include <stdio.h>
/*
功能
将两个有序序列表进行合并排序
array中a到b,已经升序排序
b+1,c已经升序排序
*/
/*归并操作*/
void merge(int array[],int a,int b,int c )
{    
    int begin1=a,end1=b;
    int begin2=b+1,end2=c;    
    int i;
    int j=begin2;
    int s=0;

    /*申请排序后的新空间c-a+1*/
    int *temp=new int[c-a+1];
    /*遍历第一组*/
    for(i=begin1; i<end1+1;i++)
    {
        /*第二组*/        
        for(;j<end2+1;j++)
        {
            /*如果第二组的元素小于第一组的元素，则复制该元素到temp*/
            if(array[i]>=array[j])
                temp[s++]=array[j];    
            else
                break;
        }
        /*不满满足时，将该元素复制，*/
        temp[s++]=array[i];
    }
    s=0;
    /*将排序后的元素复制到array中*/
    for(i=a;i<c+1;i++)
        array[i]=temp[s++];
}
/*
二路归并
功能对array数组中起始元素下标为first，结束元素下标为last，进行升序排序*/
void merge_sort(int array[],int first,int last)
{
    int middle;
    /*递归的终结条件：子区间长度为1（一个记录自然有序）*/
    if(last>first)
    {
        middle=(first+last)/2;
        merge_sort(array,first,middle);
        merge_sort(array,middle+1,last);
        merge(array,first,middle,last);    
    }
}
void main()
{
    int sort[6]={8,1,5,3,0,9};
    merge_sort(sort,0,4);
    for(int i=0;i<6;i++)
        printf("%d ",sort[i]);
    
}