【算法】归并排序

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 阅读(1038) 评论(0)  编辑 收藏 引用 所属分类: 数据结构与算法

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

导航

统计

随笔分类(55)

随笔档案(34)

网址收藏

资源下载

随笔导航

搜索

最新评论

阅读排行榜

评论排行榜