【排序算法】之归并排序

归并思想

先拆分后合并 也就是分治；
拆分合并思想具体讲解可以参考以下链接：
b站链接：

点这里：b站归并思想具体讲解

看代码

代码中的例子参考上图和下图

public class MergeSort {
    //一、拆分部分
    public static void split(int[] arr,int left,int right,int[] temp){
        //递归拆分
        if (left<right){
            int mid=(left+right)/2;
            //左递归分解
            split(arr, left, mid, temp);
            //右递归分解
            split(arr, mid+1, right, temp);
            //合并
            merge(arr,left,right,mid,temp); //这么理解就像递归就是重复干一件事 你调用执行就可
            //上面 先左递归合并 再右递归合并
        }
    }
    //二、合并部分
    /**
     * @param arr   要进行排序的初始数组
     * @param left  左序列数组的初始索引
     * @param right 右序列数组的初始索引
     * @param mid   左序列和右序列的交接地方 中间索引
     */
    public static void merge(int[] arr, int left, int right, int mid, int[] temp) {
        int i = left;//初始化i，作为左序列的初始索引
        int j = mid + 1;//初始化j，作为右序列的初始索引 mid是向下取整得来的
        int index = 0;//temp数组的当前索引
        //1.左右两边序列按照规则填充到temp数组 直到有一边处理完毕
        //循环条件 两边的数据均为处理完
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) { //左元素<=右 就把左里面的首位填充到temp
                temp[index] = arr[i];
                i++;//i后移
                index++;//index后移
            } else {//反之就填充右里面的首位
                temp[index] = arr[j];
                j++;
                index++;
            }
        }
        //当while循环结束 就有其中一边先处理完毕
        //2.把另一边中剩下的的数据直接依次填充到temp数组
            //满足哪个就去哪个循环进行填充
        while (j <= right) {
            temp[index] = arr[j];
            index++;
            j++;
        }
        while ((i <= mid)) {
            temp[index] = arr[i];
            index++;
            i++;
        }
        //3.temp数组拷贝到arr中
        //只有最后一次拷贝是把整个temp拷贝到arr数组中 前几次都是拷贝temp中的一部分
        //因为前几次的合并没有占满temp数组
        index=0;//temp索引归0；
        int tempLeft=left;
        //System.out.println("tempLeft="+tempLeft+" "+"right="+right);
            //第1次合并 tempLeft=0,right=1;
            //第2次合并 tempLeft=2,right=3;
            //第3次合并 tempLeft=0,right=3;
            //第4次合并 tempLeft=4,right=5;
            //第5次合并 tempLeft=6,right=7;
            //第6次合并 tempLeft=4,right=7;
            //第7次合并 tempLeft=0,right=7;//最后一次合并
        while (tempLeft<=right){
            arr[tempLeft]=temp[index];
            tempLeft++;
            index++;
        }
    }
    //主方法
    public static void main(String[] args) {
        int[] arr = new int[]{8, 4, 5, 7, 6, 2, 3, 9};
        int[] temp=new int[arr.length];
        split(arr,0, arr.length-1,temp);
        System.out.println(Arrays.toString(arr));

    }
}