算法排序-归并排序

何为合并排序？

集合中存在两段，每段都是有顺序的，集合中的两段分别命名为A和B，A中的首元素a和B中的首元素b比较大小，新建一个临时集合T，将A和B比较符合条件的结果a放入到T内，A段中的数组索引右移。一次类推，知道A和B其中一个完全放入T内为止。然后再将A或者B剩余数据存入T内。最后将T中的数据赋值到原集合。

合并排序两端集合有序性

如何保证集合中数据两端是有序的，采用递归方式，直至到每个子集合只有一个元素，结束递归，合并两个集合。

何为递归？

在数学与计算机科学中，指在函数定义中使用函数自身的方法，即递归算法是一种直接或者间接调用自身函数或者方法的算法。

递归三大要素

明确函数要做什么？不管函数里面的代码，要明白函数的具体作用。
寻找递归结束条件。需要找出递归结束的参数，然后返回结果。
找出函数的等价关系。要不断的缩小参数范围，缩小之后，我们可以通过一些辅助的变量或操作，是原函数的结果不变。

算法核心点：

计算中间值是，采用left + (right-left)/2 而非 (left+right)/2，避免两个int相加，超过int范围。
临时集合大小，一定要注意初始化时集合大小和向原集合赋值时的下标。
判断集合两段的结束条件。
集合两段其中一段结束后，必须把段中其余元素加入到临时集合中。

归并排序，从小到大代码样例

package com.booby.algorithm.merge;

import com.booby.algorithm.utils.Utils;

/**
 * 功能描述: 归并排序，从小到大
 *
 * @author: lizt
 * @date: 2020/8/23 15:51
 **/

public class MinToMax {

    public static final Integer[] arr = {3,5,7,9,1,2,5,8,10};

    public static void sorted(Integer[] arr, int left, int right){
        if (left == right){
            return;
        }
        // 一般写 （left + right）/ 2  容易超出整型范围
        int mid = left + (right-left)/2;
        sorted(arr, left, mid);
        sorted(arr, mid + 1, right);
        merge(arr, left, mid + 1, right);
    }
    public static void merge(Integer[] arr, int leftPtr, int rightPtr, int rightBound){
        Integer[] temp = new Integer[rightBound - leftPtr + 1];
        int mid = rightPtr - 1;
        int index = 0;
        int left = leftPtr;
        int right = rightPtr;
        while (left <= mid && right <= rightBound) {
            if (arr[left] <= arr[right]) {
                temp[index] = arr[left];
                left++;
                index++;
            }else {
                temp[index] = arr[right];
                index++;
                right++;
            }
        }
        while (left <= mid){
            temp[index] = arr[left];
            left++;
            index++;
        }

        while (right <= rightBound){
            temp[index] = arr[right];
            right++;
            index++;
        }

        for (int i = 0; i < temp.length; i++) {
            arr[leftPtr + i] = temp[i];
        }

    }
    public static void main(String[] args) {
        sorted(arr, 0, arr.length -1);
        Utils.print(arr);
    }
}

归并排序，从大到小代码样例

package com.booby.algorithm.merge;

import com.booby.algorithm.utils.Utils;

/**
 * 功能描述:
 *
 * @author: lizt
 * @date: 2020/8/23 16:54
 **/

public class MaxToMin {

    public static final Integer[] arr = {3,5,7,9,1,2,5,8,10};

    public static void sorted(Integer[] arr, int left, int right){
        if (left == right){
            return;
        }
        int mid = left + (right - left)/2;
        sorted(arr, left, mid);
        sorted(arr, mid + 1, right);
        merge(arr, left, mid + 1, right);
    }

    public static  void merge(Integer[] arr, int lefePtr, int rightPtr, int rightBound){

        Integer[] temp = new Integer[rightBound - lefePtr + 1];
        int left = lefePtr;
        int right = rightPtr;
        int index = 0;
        int mid = rightPtr -1;
        while (left <= mid && right <= rightBound){
            if (arr[left] >= arr[right]){
                temp[index] = arr[left];
                index++;
                left++;
            }else {
                temp[index] = arr[right];
                index++;
                right++;
            }
        }
        while (left <= mid){
            temp[index] = arr[left];
            index++;
            left++;
        }
        while (right <= rightBound){
            temp[index] = arr[right];
            index++;
            right++;
        }
        for (int i = 0; i < temp.length; i++) {
            arr[lefePtr + i] = temp[i];
        }
    }
    public static void main(String[] args) {
        sorted(arr, 0, arr.length-1);
        Utils.print(arr);
    }
}

归并排序稳定性？

因为归并排序集合中两段的元素比较，并赋值到临时集合。相同值不改变元素顺序。所以为稳定排序

归并排序复杂度

平均时间复杂度	最坏时间复杂度	最好时间复杂度	空间复杂度	稳定性
nlog₂ⁿ	nlog₂ⁿ	nlog₂ⁿ	n	稳定