归并排序（MergeSort）

1. 基本介绍：

   是利用归并的思想实现的排序方法，该算法采用经典的分治策略（先分再治）

2. 归并排序示意图

1. 代码实现——时间复杂度（1s_8百万）

package DataStructures.Sort;

import java.util.Arrays;

public class MergeSort {
    public static void main(String[] args) {
        int arr[] = {8, 4, 7, 5, 1, 3, 6, 2};
        int temp[] = new int [arr.length];  //说明归并排序需要一个额外的开销
        mergeSort(arr,0,arr.length-1,temp);
        System.out.println("归并排序后="+ Arrays.toString(arr));
    }
    //分+合方法
    public static void mergeSort(int arr[],int left,int right,int temp[]){
        if (left<right){
            //中间的索引
            int mid = (left+right)/2;
            //向左递归进行分解
            mergeSort(arr,left,mid,temp);
            /*
            System.out.println("left="+left+" mid="+mid+" right="+right);
            merge(arr,left,mid,right,temp);
            System.out.println(Arrays.toString(arr));
            System.out.println("------");
             */
            //向右递归进行分解
            mergeSort(arr,mid+1,right,temp);
            /*
            System.out.println("left="+left+" mid="+mid+" right="+right);
            */
            merge(arr,left,mid,right,temp);
            /*
            System.out.println(Arrays.toString(arr));
            System.out.println("~~~~~~~~~~~");
             */

        }

    }

    //合并的方法
    /**
     * @param arr   原始数组
     * @param left  左边索引
     * @param mid   中间索引
     * @param right 右边索引
     * @param temp  中转数组
     */
    public static void merge(int arr[], int left, int mid, int right, int temp[]) {
        int i = left;//初始化i，左边有序序列的初始索引
        int j = mid + 1; //初始化j，表示右边有序序列的初始索引
        int t = 0;  //指向temp数组的当前索引

        //（1）
        //先把左右两边（有序）的数组按照规则填充到temp数组
        //直到左右两边的有序序列，有一边处理完毕为止
        while (i <= mid && j <= right) {
            //如果左边有序序列的当前元素，小于等于右边有序序列的当前元素
            //即将左边的当前元素，拷贝到temp数组中
            //然后t++；i++
            if (arr[i] <= arr[j]) {
                temp[t] = arr[i];
                t += 1;
                i += 1;
            } else {
                //右边的有序序列小于左边的当前元素
                temp[t] = arr[j];
                t += 1;
                j += 1;
            }
        }

        //（2）
        //把有剩余数据的一边的数据依次填充到temp中
        while (i <= mid) {
            //左边有序序列还有剩余
            temp[t] = arr[i];
            t += 1;
            i += 1;
        }
        while (j <= right) {
            //右边有序序列还有剩余
            temp[t] = arr[j];
            t += 1;
            j += 1;
        }

        //（3）
        //将temp数组的元素拷贝到arr
        //注意：不是每次都拷贝全部
        t = 0;
        int templeft = left;
       // System.out.println("templeft="+templeft+" right="+right);
        while(templeft <= right){
            arr[templeft] = temp[t];
            t +=1;
            templeft +=1;
        }
        //System.out.println("----");
    }
}

2. 注释一下代码的两个方法

//分+合方法
    public static void mergeSort(int arr[],int left,int right,int temp[]){
        if (left<right){
            
            int mid = (left+right)/2;
            
            mergeSort(arr,left,mid,temp);
           
            mergeSort(arr,mid+1,right,temp);
            
            merge(arr,left,mid,right,temp);
        }

    }
//详见视图三（手绘）
//运行顺序是先左后右
//当左边运行到0~0时，不能运行，弹出，接着运行1~1，不能运行，弹出
//弹出再0~1中，按照从上到下的顺序运行code，就到了merge()方法了
//merge()方法提供了至少两个数的比较，于是将0~1上的数排序
//0~1运行结束后，弹出，接着运行2~3下的两个2~2和3~3
//2~2和3~3不能运行弹出后，再2~3下运行merge()方法，排序2~3
//现在0~1和2~3运行完毕，弹出后接着运行0~3的merge()方法
//注意，此时0~1和2~3有了自己的从小到大的顺序
//0~3排序完毕后到了4~7下的4~5下的4~4及5~5和6~7下的6~6和7~7
//每次弹出都完成了对一个方向的排序
//当4~5和6~7排序完毕后就排序4~7
//4~7排序完毕后就排序0~7

 //合并的方法
    /**
     * @param arr   原始数组
     * @param left  左边索引
     * @param mid   中间索引
     * @param right 右边索引
     * @param temp  中转数组
     */
    public static void merge(int arr[], int left, int mid, int right, int temp[]) {
        int i = left;
        int j = mid + 1; 
        int t = 0;  
        //（1）
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[t] = arr[i];
                t += 1;
                i += 1;
            } else {
                temp[t] = arr[j];
                t += 1;
                j += 1;
            }
        }
        //（2）
        while (i <= mid) {
            temp[t] = arr[i];
            t += 1;
            i += 1;
        }
        while (j <= right) {
            temp[t] = arr[j];
            t += 1;
            j += 1;
        }
        //（3）
        t = 0;
        int templeft = left;
        while(templeft <= right){
            arr[templeft] = temp[t];
            t +=1;
            templeft +=1;
        }
    }
}
//merge()方法要好理解一些，他的作用很简单，就是比较后添加进入temp排序
//排序完毕后返回到arr[]中，完成arr[]的排序
//这里merge的左和右就是mergesort()方法拆分出来的（至少两个数）
//左边的索引和右边的索引