合并排序的递归实现代码,Java代码库,德仔网

代码语言

代码分类

【Java】合并排序的递归实现

作者:宝清 / 发布于2016/4/20/ 563

package com.stu.find;
 
public class MergeSort {
    public   void  merge(int []A,int p,int q,int r)
    {
        int nl=q-p+1;
        int nr=r-q;
        int [] rArr=new int[nl+1];
        int [] lArr=new int [nr+1];
 
        for(int i=0;i<nl;i++)
        {
            rArr[i]=A[i+p];
        }
 
        for(int j=0;j<nr;j++)
        {
            lArr[j]=A[j+q+1];
        }
 
 
        rArr[nl] = Integer.MAX_VALUE;  
        lArr[nr] = Integer.MAX_VALUE;  
        int n=0;
        int m=0;
        //接下来进行比较
        for(int i=p;i<=r;i++)
        {
            if(m<=nl&&n<=nr)
            {
                //A[i]=lArr[m]<rArr[n]?lArr[m++]:rArr[n++];
 
                if(lArr[m]<rArr[n])
                {
                    A[i]=lArr[m];
                    m++;
                }
                else
                {
                    A[i]=rArr[n];
                    n++;
                }
            }
            else
            {
                if(m<nl)
                {
                    A[i]=lArr[m];
                    m++;
                }
                else
                {
                    A[i]=rArr[n];
                    n++;
                }
            }
        }
 
    }
 
    public void mergerSort(int []A,int p,int r)
    {   if(p == r){  
        return;  
    }else
    {
        int q=(r+p)/2;
 
        mergerSort(A,p,q);
        mergerSort(A,q+1,r);
        merge(A,p,q,r);
    }
 
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int a[]={1,3,2,5,6,4,8,7,9,11,10};
        for(int i=0;i<a.length;i++)
        {
            System.out.print(a[i]);
        }
        System.out.println();
        int r=a.length-1;
        System.out.println("长度"+r);
 
        MergeSort MS=new MergeSort();
        MS.mergerSort(a,0,r);
 
        for(int i=0;i<a.length;i++)
        {
            System.out.print(a[i]+"    ");
        }
        System.out.println();
    }
 
}

试试其它关键字

　合并排序　

同语言下

可能有用的

宝清贡献的其它代码(78)