1. package com.atguigu.sort;
    3. import java.util.Arrays;
    4. import java.util.Date;
    6. /**
    7.  * @author Dxkstart
    8.  * @create 2021-10-12-20:06
    9.  */
    10. public class MergeSort {
    11.     public static void main(String[] args) {
    12.         int[] arr = {8,4,5,7,1,3,6,2};
    13.         int[] temp = new int[arr.length];//归并排序需要一个额外的空间
    14.         mergeSort(arr,0, arr.length - 1,temp);
    16.         System.out.println(Arrays.toString(arr));
    18.     }
    21.     //分+合方法
    22.     public static void mergeSort(int[] arr, int left, int right, int[] temp) {
    23.         if (left < right) {
    24.             int mid = (left + right) / 2;//中间索引
    25.             //向左递归分解
    26.             mergeSort(arr, left, mid, temp);
    27.             //向右递归分解
    28.             mergeSort(arr, mid + 1, right, temp);
    29.             //合并
    30.             merge(arr, left, mid, right, temp);
    31.         }
    32.     }
    35.     //合并的方法
    37.     /**
    38.      * @param arr   排序的原始数组
    39.      * @param left  左边有序列的初始索引
    40.      * @param mid   中间索引
    41.      * @param right 右边索引
    42.      * @param temp  做中转的数组
    43.      */
    44.     public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
    45.         int i = left;//初始化i,左边有序序列的初始索引
    46.         int j = mid + 1;//初始化j,右边有序序列的初始索引
    47.         int t = 0;//指向temp数组的当前索引
    49.         //(一)
    50.         //先把左右两边（有序）的数据暗战规则填充到temp数组
    51.         //直到左右两边的有序序列，有一边处理完毕为止
    52.         while (i <= mid && j <= right) {
    53.             //如果左边的有序序列的当前元素，小于等于右边有序序列的当前元素
    54.             //即将左边的当前元素，拷贝到temp数组
    55.             //然后 t++,i++
    56.             if (arr[i] <= arr[j]) {
    57.                 temp[t] = arr[i];
    58.                 t++;
    59.                 i++;
    60.             } else {
    61.                 temp[t] = arr[j];
    62.                 t++;
    63.                 j++;
    64.             }
    65.         }
    67.         //(二)
    68.         //把有剩余数据的一边的数据一次全部填充到temp
    69.         while (i <= mid) {//说明左边的有序序列还有剩余的元素
    70.             temp[t] = arr[i];
    71.             t++;
    72.             i++;
    73.         }
    75.         while (j <= right) {//说明右边的有序序列还有剩余的元素
    76.             temp[t] = arr[j];
    77.             t++;
    78.             j++;
    79.         }
    81.         //(三)
    82.         //将temp数组的元素拷贝到arr
    83.         //注意，并不是每次都拷贝所有
    84.         t = 0;
    85.         int tempLeft = left;
    86.         //第一次合并 tempLeft = 0,right = 1
    87.         //最后一次合并 tempLeft = 0, right = 7
    88.         while (tempLeft <= right) {
    89.             arr[tempLeft] = temp[t];
    90.             t++;
    91.             tempLeft++;
    92.         }
    94.     }
    95. }