Java实现归并排序

归并排序主要使用了分治的思想，分治是指将问题分为若干个子问题，解决子问题后合并。

归并排序是将数组分为两个部分，依次递归直到数组只剩一个元素，然后合并

public class template {
    public static void main(String args[]){
        int N = 10;
        int [] a =new int[N];
        for(int i =0;i<a.length;i++){
            a[i]= N-i;
        }
        //生成长度为N的倒序数组，修改N即可修改数组长度
        mergesort(a, 0, N-1);
        for(int i =0 ;i<a.length;i++){
            System.out.print(a[i]+"\n");
        }
    }
    //归并排序
    public static void mergesort(int[] A,int l,int r){
        int m;
        m=(l+r)/2;   //分为两部分
        if(l<r){     //当子数组元素不为一时，不停递归分解问题
            mergesort(A, l, m);        //对左边的部分进行递归
            mergesort(A, m+1, r);      //对有右边的部分进行递归
            merge(A, l, m, r);         //合并
        }
    }
    //合并过程，由于两个子数组均已经排序完毕，只需一一比较两个子数组中的每个元素，然后依次放入原数组中。
    public static void merge(int[] A,int l,int m,int r){
        int n1 = m-l+1;
        int n2 = r-m;
        int [] L = new int[n1];
        int [] R = new int[n2];
        for(int i = 0;i<n1;i++){
            L[i] = A[l+i];
        }
        //将左半部分放入一个新数组
        for(int i = 0;i<n2;i++){
            R[i] = A[m+i+1];
        }
        //将右半部分放入一个新数组,注意数组下标和实际位置之间的差别，避免越出数组下界或者上界
        int i =0;
        int j =0;
        //在合并的过程中需要注意两个子数组是否为空，如果其中一个为空则无需比较，只需将另一个数组中的元素依次放入原数组
        for(int k=l;k<=r;k++){
            if(i<n1&&j<n2){         
                if(L[i]>=R[j]){
                    A[k]= R[j];
                    j++;
                }
                else{
                    A[k]=L[i];
                    i++;
                }
            }
            //两个子数组都不为空的情况，比较左边和右边的最小元素，然后将更小的放入原数组
            else if(i>=n1){
                A[k] = R[j];
                j++;
            }
            else{
                A[k] = L[i];
                i++;
            }
            //如果其中一个已经全部放入原数组，只需顺序将剩余元素依次放入数组
        }
    }
}