排序—归并排序

基本思想

归并排序(Merge Sort)的基本思想是：分治
网上有很多关于基本思想的介绍，不想多说，感觉也记不住。

我们设想一下，如果有两个有序数组A,B，写一个方法merge，使其合并成一个有序的数组C，步骤如下：

创建一个临时数组C，长度为A,B数组长度之和。
从数组A,B的0下标处开始遍历，取A[indexA],B[indexB]两个元素，较小(假设从小到大排序)的元素放入临时数组，较大元素继续和对方下一个元素比较，直到某一个数组的元素全部放入临时数组。
将没有处理完的数组元素全部放到临时数组的后面。
返回临时数组。

上面的Merge方法中包含了排序的过程。现在的问题是如何得到两个有序的数组？很简单，采用分治的方法，自上而下，每次取一半，那么最终的得到的相邻两个元素各自形成数组，数组长度=1，自然有序，进行merge，得到长度=2的有序数组，再和同样相邻的长度=2的数组merge，得到长度=4,…….，最终达到有序。

图解

做个拆解图：
归并动态拆解

归并算法动态过程:

实现(java)

import java.util.Arrays;
/**
 * Created by Numen_fan on 2021/01/10
 * desc: 归并排序
 */
public class MergeSort {

    public static void main(String[] args) {
        int[] arr = {1, 2, 4, -1, 3, 4, 6, 8, 0, -2, 5};
        System.out.println(Arrays.toString(mergeSort(arr)));
    }

    /**
     * 采用递归处理
     * (分解)
     */
    private static int[] mergeSort(int[] sourceArr) {
        if (sourceArr.length < 2) { // 这里处理递归结束条件，当被拆解到只有一个元素时，一个元素必定有序
            return sourceArr;
        }
        int mid = sourceArr.length / 2;
        // 将sourceArr拆分成左右两部分
        int[] left = Arrays.copyOfRange(sourceArr, 0, mid); // 不包含mid处的元素
        int[] right = Arrays.copyOfRange(sourceArr, mid, sourceArr.length);
        // 合并"排序后"的左右部分
        return merge(mergeSort(left), mergeSort(right));
    }

    /**
     * 归并两个"有序"的数组
     * @return 合并后的新的数组
     */
    private static int[] merge(int[] arr1, int[] arr2) {
        // 1 处理边界情况
        if (arr1 == null || arr1.length == 0) {
            return arr2 == null || arr2.length == 0 ? null : arr2;
        }
        if (arr2 == null || arr2.length == 0) {
            return arr1;
        }

        int[] resArr = new int[arr1.length + arr2.length];
        int resIndex = 0; // resArr的下标
        int arr1Index = 0;
        int arr2Index = 0;
        // 2 做合并
        while (arr1Index < arr1.length && arr2Index < arr2.length) {
            resArr[resIndex++] = arr1[arr1Index] <= arr2[arr2Index] ?
                    arr1[arr1Index++] : arr2[arr2Index++]; // 三个下标做自加
        }
        // 3 处理剩余的数组（这里需要清楚，arr1Index或者arr2Index是对应数组中还没有处理的元素下标）
        if (arr1Index < arr1.length) {
            System.arraycopy(arr1, arr1Index, resArr, resIndex, arr1.length - arr1Index);
        }
        if (arr2Index < arr2.length) {
            System.arraycopy(arr2, arr2Index, resArr, resIndex, arr2.length - arr2Index);
        }
        return resArr;
    }

}

复杂度

时间复杂度：$O(nlogn)$
空间复杂度：$O(n)$
稳定性：稳定

参考资料

https://www.runoob.com/w3cnote/merge-sort.html

最后

此文若有出入，请指出！
此致，敬礼！