随笔 - 87  文章 - 279  trackbacks - 0
<2024年11月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

潜心看书研究!

常用链接

留言簿(19)

随笔分类(81)

文章分类(89)

相册

ACM OJ

My friends

搜索

  •  

积分与排名

  • 积分 - 214330
  • 排名 - 116

最新评论

阅读排行榜

评论排行榜

/*
合并排序 
*/

#include 
< iostream >
using   namespace  std;

template 
< class  T >
void  Merge(T c[], T d[],  int  l,  int  m,  int  r) 
{
    
int  i  =  l, j  =  m  +   1 , k  =  l;
    
while  (i  <=  m  &&  j  <=  r)  {
        
if  (c[i]  <=  c[j])  {
            d[k
++ =  c[i ++ ];
        }
  else   {
            d[k
++ =  c[j ++ ];
        }

    }

    
if  (i  >  m)  {
        
for  (; j  <=  r; j ++ {
            d[k
++ =  c[j];
        }

    }
  else   {
        
for  (; i  <=  m; i ++ {
            d[k
++ =  c[i];
        }

    }

}

template 
< class  T >
void  Copy(T c[], T d[],  int  l,  int  r) 
{
    
int  i;
    
for  (i = l; i <= r; i ++ {
        c[i] 
=  d[i];        
    }

}

template 
< class  T >
void  MergePass(T a[], T b[],  int  l,  int  r)
{
    
int  m;
    
if  (l  <  r)  {
        m 
=  (l  +  r)  /   2 ;
        MergePass(a, b, l, m);
        MergePass(a, b, m
+ 1 , r);
        Merge(a, b, l, m, r);
        Copy(a, b, l, r); 
    }

}

template 
< class  T >
void  MergeSort(T a[],  int  n)
{
    T 
* =   new  T[n];
    MergePass(a, b, 
0 , n - 1 );
}


int  main()
{
    
int  i, j;
    
int  a[]  =   { 5 9 3 7 1 } ;
    MergeSort(a, 
5 );
    
for  (i = 0 ; i < 5 ; i ++ {
        printf(
" %d  " , a[i]);
    }

    printf(
" \n " );
    system(
" pause " );
}

posted on 2006-10-10 01:11 阅读(1481) 评论(1)  编辑 收藏 引用 所属分类: 数据结构与算法

FeedBack:
# re: 合并排序 2006-10-10 01:46 
while (i <= m && j <= r) {
if (c[i] <= c[j]) {
d[k ++ ] = c[i ++ ];
} else {
d[k ++ ] = c[j ++ ];
ni = m - i + 1; //可以求出逆序数
}
}   回复  更多评论
  

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