[数据结构与算法]Java归并排序

Java实现归并排序：

import java.util.Arrays;

public class GuiBing {

    public static void main(String[] args) {
        //归并排序也是利用递归进行的排序
        int []arr=new int[]{2,6,3,65,9,8,7,50};
        Process(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));

    }

    public static void Process(int []arr,int L,int R){
        //归并排序首先要实现不同部分的排序 ，然后进行整合
        if(L==R){
            return;     //这个可以理解为我们递归地结束条件
        }
        int M=L+((R-L)>>1); //>>1   就是除以2的意思   使用位运算比使用算数运算要快很多

        Process(arr, L,M);
        Process(arr, M+1,R);  //左右的两个递归实现的就是对数组的左右两侧进行分割   merge()方法才是最后实现排序的主力
        merge(arr,L,M,R);


    }

    private static void merge(int[] arr, int l, int M,int r) {
        //创建一个新的数组来作为合并的新数组
        int []  array=new int[r-l+1];
        int i=0;
        int x=l;
        int y=M+1;
        while(x<=M&&y<=r){
                array[i++]=arr[x]<=arr[y]?arr[x++]:arr[y++];   //三元表达式进行赋值

        }
        while(x<=M){
            array[i++]=arr[x++];
        }
        while(y<=r){    //相等的时候也可以进行这个赋值的操作
            array[i++]=arr[y++];
        }

        //最后将原先的数组进行赋值
        for (int j = 0; j <array.length ; j++) {
            arr[l+j]=array[j];
        }
    }
}