ghost79

导航

<2009年9月>
日一二三四五六
303112345
6789101112
13141516171819
20212223242526
27282930123
45678910

统计

留言簿(0)

随笔分类

随笔档案

文章档案

搜索

最新评论

阅读排行榜

评论排行榜

合并排序之C++实现

void merge( int *A, int p, int q, int r )
{
    int n1 = q - p + 1,
        n2 = r - q,
        *L = new int[ n1 + 1 ],
        *R = new int[ n2 + 1 ];

    for( int k = 0; k < n1; k ++ ) L[ k ] = A[ p + k ];
    for( int k = 0; k < n2; k ++ ) R[ k ] = A[ q + k + 1 ];
    L[ n1 ] = 2147483647, R[ n2 ] = 2147483647;

    int i = 0, j = 0;
    for( int k = 0; k < r - p + 1; k ++ )
        if( L[ i ] <= R[ j ] )
        {
            A[ p + k ] = L[ i ];
            i ++;
        }
        else
        {
            A[ p + k ] = R[ j ];
            j ++;
        }

    delete []L;
    delete []R;
}

void merge_sort( int *A, int p, int r )
{
    if( p < r )
    {
        int q = ( p + r ) / 2;
        merge_sort( A, p, q );
        merge_sort( A, q + 1, r );
        merge( A, p, q, r );
    }
}

posted on 2009-09-10 10:57 C家家 阅读(62) 评论(0)  编辑 收藏

评论

标题  
姓名  
主页
内容   
请输入验证码:
*
  登录  使用高级评论  Top 订阅回复  取消订阅
[使用Ctrl+Enter键可以直接提交]