算法导论学习笔记--分治法

   怀着莫大的敬意和勇气购买了传说中的算法导论,是该开始我的求职准备之路了.希望自己能够坚持把这本书啃完.每个算法都尽量的实现下.
   ch2的选择和冒泡排序就不写了^_^.分治搞了半天才搞出来,惭愧!!!
  

[root@mip-123456 algorithm]# cat merger.c
#include <stdio.h>
#define N 10

int a[N]={10,8,7,5,9,1,3,6,4,2};
void merge(int a[],int p,int q,int r)
{
    int n1=q-p+1;
    int n2=r-q;
    int L[n1+1];
    int R[n2+1];
    int m,n;
    for(m=0;m<n1;m++)
        L[m]=a[p+m];
    for(n=0;n<n2;n++)
        R[n]=a[q+n+1];

    L[n1]=2147483647;
    R[n2]=2147483647;
    int i = 0;
    int j = 0;
    int k = 0;
    for(k=p;k<=r;k++)
    {
        if(L[i]<=R[j])
        {
            a[k]=L[i];
            i++;
        }
        else
        {
            a[k]=R[j];
            j++;
        }
    }
}

void mergesort(int a[],int p,int r)
{
    int q;
    if(p<r)
    {
        q=(p+r)/2;
        mergesort(a,p,q);
        mergesort(a,q+1,r);
        merge(a,p,q,r);
    }
    
}

int main()
{
   int i;
   printf("before sort:\n");
   for(i=0;i<N;i++)
   {
      printf("%5d",a[i]);
   }
   printf("\nafter sort:\n");
   mergesort(a,0,N-1);
   for(i=0;i<N;i++)
   {
      printf("%5d",a[i]);
   }

   getchar();
   return 0;
}
[root@mip-123456 algorithm]# ./merger
before sort:
   10 8 7 5 9 1 3 6 4 2
after sort:
    1 2 3 4 5 6 7 8 9 10