简介

归并排序（MERGE-SORT）是利用 归并 的思想实现的排序方法，该算法采用经典的 分治 （divide-and-conquer）策略（分治法将问题 分 (divide) 成一些小的问题然后递归求解，而 治(conquer) 的阶段则将分的阶段得到的各答案”修补”在一起，即分而治之 )。

图解

由上图我们可以看出，归并排序主要分两部分，分和治。

分：将待排序一直拆分，直到无法拆分为止

治：将拆分好的数据进行比对排序并合并

代码实现

 package com.zyp.sort;

import java.util.Arrays;

/**
 * 归并排序
 *
 * @author zyp
 * @create 2022/2/17
 */
public class MergerSort {
    public  static   void  main(String[] args) {
        int[] array = new int[]{8, 4, 5, 7, 1, 3, 6, 2};
        int[] tempArray = new int[array.length];
        divideAndRule(array, 0, array.length - 1, tempArray);
        System.out.println(Arrays.toString(array));

    }

    /**
     * 分治
     *
     * @param array     待排序数组
     * @param left      数组的开始位置
     * @param right     数组的结束位置
     * @param tempArray 临时数组
     */
    public static void divideAndRule(int[] array, int left, int right, int[] tempArray) {
        if (left < right) {
            int mid = (left + right) / 2;
            divideAndRule(array, left, mid, tempArray);
            divideAndRule(array, mid + 1, right, tempArray);
            merger(array, left, mid,right,tempArray);
        }

    }

    /**
     * 归并
     *
     * @param array     待排序数组
     * @param left      数组的开始位置
     * @param mid       两个有序数组的中间值
     * @param right     数组的结束位置
     * @param tempArray 临时数组
     */
    public static void merger(int[] array, int left, int mid, int right, int[] tempArray) {
        int index = 0;
        int l = left;
        int m = mid+1;
        while (l <= mid && m <= right) {
            if (array[l] > array[m]) {
                tempArray[index] = array[m];
                m++;
                index++;
            } else {
                tempArray[index] = array[l];
                l++;
                index++;
            }
        }
        //将左边剩余的数据放入临时数组中
        while (l <= mid) {
            tempArray[index] = array[l];
            l++;
            index++;
        }

        //将右边剩余的数据放入临时数组中
        while (m <= right) {
            tempArray[index] = array[m];
            m++;

            index++;
        }

        int t = 0;
        //将临时数组中的元素拷贝到数组中
        for (int i = left; i <= right; i++) {
            array[i] = tempArray[t];
            t++;
        }
    }
}