[基础算法复习]归并排序


static   void  _merge( int   * src, int  begin, int  end);

int  merge_sort( int   * array, int  begin, int  end)
{
    
if (array == NULL || begin > end)  return   0 ;

   
int  mid  =  begin + (end - begin) / 2 ;
   merge_sort(src,begin,mid);
   merge_sort(src,mid
+ 1 ,end);
   _merge(src,begin,end);

    return 1;
}

static   void  _merge( int   * src, int  begin, int  end)
{
    
int  mid  =  begin + (end - begin) / 2 ;

    
int  b1  =  begin;
    
int  e1  =  mid;
    
int  b2  =  mid + 1 ;
    
int  e2  =  end;

    
int   * dest  =  malloc( sizeof ( int ) * (end - begin + 1 ));
    
if (dest == NULL)  return ;

    
int  i1;
    
int  i2;
    
int  i;
    
for (i1 = b1,i2 = b2,i = begin;i1 <= e1 && i2 <= e2 && i <= end; ++ i){
        
if (src[i1] < src[i2]){
            dest[i
- begin]  =  src[i1];
            i1
++ ;
        }
else {
            dest[i
- begin]  =  src[i2];
            i2
++ ;
        }
    }

    
for (;i <= end && i1 <= e1; ++ i, ++ i1)
       dest[i
- begin]  =  src[i1];
    
for (;i <= end && i2 <= e2; ++ i, ++ i2)
       dest[i
- begin]  =  src[i2];

    
for (i = begin;i <= end; ++ i)
        src[i] 
=  dest[i - begin];

    free(dest);
}


做一些小优化,只创建一次临时数组。
void _mergesort(int *array,int *tmp,int start,int end);

void mergesort(int *array,int len)
{
    
int i,*tmp;

    
if(array==NULL||len==0)
        
return;

    tmp 
= (int*)malloc(sizeof(int)*len);

    _mergesort(array,tmp,
0,len-1);

    free(tmp);
}

void _mergesort(int *array,int *tmp,int start,int end)
{
    
int mid = (start+end)/2;
    
int i,j,k;

    
if(start>=end)
        
return;
    
    _mergesort(array,tmp,start,mid);
    _mergesort(array,tmp,mid
+1,end);

   i 
= start;
   j 
= mid+1;

   
for(k=start;k<=end&&i<=mid&&j<=end;++k){
       
if(array[i]<array[j]){
           tmp[k] 
= array[i];
           i
++;
       }
else{
           tmp[k]
= array[j];
           j
++;
       }
   }

   
for(;i<=mid;++i)
       tmp[k
++]=array[i];

   
for(;j<=end;++j)
       tmp[k
++]=array[j];
      
  memcpy(
&array[start],&tmp[start],sizeof(int)*(end-start+1)); 
}
   

posted on 2009-07-15 11:46 YZY 阅读(226) 评论(0)  编辑 收藏 引用 所属分类: Algorithm基础算法


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

<2009年7月>
2829301234
567891011
12131415161718
19202122232425
2627282930311
2345678

统计

常用链接

留言簿(2)

随笔分类

随笔档案

搜索

积分与排名

最新评论

阅读排行榜