【算法】归并排序

Java实现
//归并排序
    public static void merge(int[] data,int p,int q,int r)
    {
        int[] B=new int[data.length];
        int s=p;
        int t=q+1;
        int k=p;
        while(s<=q&&t<=r)
        {
            if(data[s]<=data[t])
            {
                B[k]=data[s];
                s++;
            }
            else
            {
                B[k]=data[t];
                t++;
            }
            k++;
        }
        if(s==q+1)
        {
            B[k++]=data[t++];
        }
        else
        {
            B[k++]=data[s++];
        }
        
        for(int i=p;i<=r;i++)
        {
            data[i]=B[i];
        }
    }
    /*
    //方法一
    public static void merge_sort(int[] data,int size)
    {
        int t=1;//每组元素个数
        while(t<size)
        {
            int s=t;//本次循环每组元素个数
            t=2*s;
            int i=0;
            while(i+(t-1)<size)
            {
                merge(data,i,i+(s-1),i+(t-1));
                i=i+t;
            }
            if(i+(s-1)<size-1)
            {
                merge(data,i,i+(s-1),size-1);
            }
        }
    }*/
    //方法二
    public static void merge_sort(int[] data,int left,int right)
    {
        int t=1;//每组元素个数
        int size=right-left+1;
        while(t<size)
        {
            int s=t;//本次循环每组元素个数
            t=2*s;
            int i=left;
            while(i+(t-1)<size)
            {
                merge(data,i,i+(s-1),i+(t-1));
                i=i+t;
            }
            if(i+(s-1)<right)
            {
                merge(data,i,i+(s-1),right);
            }
        }
    }

posted on 2009-04-25 23:41 intrl 阅读(1196) 评论(0)  编辑 收藏 引用 所属分类: 数据结构与算法

只有注册用户登录后才能发表评论。
<2009年4月>
日一二三四五六
2930311234
567891011
12131415161718
19202122232425
262728293012
3456789

导航

统计

随笔分类(55)

随笔档案(34)

网址收藏

资源下载

随笔导航

搜索

最新评论

阅读排行榜

评论排行榜