#include
void combin(int num[],int r,int p,int q)  /*合并过程*/
{   
    int lift[q-p],right[r-q+1],i,j,k;
    for(i=0;i<Q-P;I++){
        lift[i]=num[p+i];
    }
    for(i=0;i<R-Q+1;I++){
        right[i]=num[q+i];
    }
    i=0;j=0;
    for(k=p;k<=r;k++){
     if(i<Q-P&&J<R-Q+1){
        if(lift[i]>right[j]){
            num[k]=right[j];
            j++;
        }
        else{
            num[k]=lift[i];
            i++;
        }
      }
    else if(i==q-p){
          num[k]=right[j];
          j++;
      }
      else if(j==r-q+1){
          num[k]=lift[i];
          i++;
      }
      }
}
void combin_sort(int num[],int n,int p )   ;----------------递归分解合并过程
{   
       int q;
       q=(n+p)/2;
       if(p<N){
        combin_sort(num,q,p);                  
        combin_sort(num,n,q+1);
        combin(num,n,p,q+1);
    }
      
}
int main(int argc, char *argv[])               /*对一串无序的数据 进行排序 */
{
    int num[20],i=0,j;
    printf("please insert num insert q to quit\n");
    while(scanf("%d",num+i)==1){
        i++;
    }
    if(i>1){
      combin_sort(num,i-1,0);
    }
    for(j=0;j<I;J++)
    printf("%d ",num[j]);
    printf("done\n");
    return 0;
}

分治的中心思想为
满足条件 1个问题可以被分解成N个相同问题 。
求解过程 由N个问题经过组合而得到要求解的问题 。
分治包含操作过程
1.分解过程 2.合并过程
分解过程 是一个典型的递归思想
既然是递归 那么就应该有递归函数（函数完成动作部分），递归终止条件（原子操作），靠近递归终止条件的表达式

分治算法的递归函数式  x={a1,a2..........an} 代表问题集合  用F(1,N) （n>=1） 将其1分为二就得到集合 f(1,n/2)和f(n/2+1,n)
f(1,n)=f(1,n/2) combin f(n/2+1,n)   
然后对 f(1,n/2)和 f(n/2+1,n) 进行一分为二
归纳出
F(x,y)=f(x,y/2) combin f(y/2+1,y)   f(x,y/2)  表示的是集合{x.......y/2}  f(y/2+1,y) 表示的集合{y/2+1..............y}
当x，y的值  是有上一个（a,b）给出的 如果f(x,y)是左边部分 那么有表达式  x=a y=(a+b)/2 如果是右半部分就会是x=(a+b)/2+1,y=b
这么个关系存在 y的取值是上一个a,b的中间。
原子操作部分的确定
那么原子操作 怎么来确定对f(x,y)不能再分解条件 (x+y)/2=x和(x+y)/2=y 成立  注意这个/ 是取商运算，在整数运算，
如果余数是0 可以演化出x=y的  所以得到 原子操作的判断条件是 x=y
因为x<=y的，所以只要x<Y就要进行递归分解

递归靠近条件表达式就是  取中间量表达式  x+y/2

完成动作部分就是合并 过程  那么合并怎么来实现
合并规则
在上面排序程序 是将 两个排好序的 数组进行合并  F(a,(a+b)/2)和F（(a+b)/2+1,b）两个数组集合元素 进行插入插入排序u 得到 F(a,b)

个人浅见 希望对大家有用

[ 本帖最后由 zhu224039 于 2012-10-2 00:57 编辑 ]