归并排序

平均时间复杂度：O(nlogn)
最坏时间复杂度：O(nlogn)
最优时间复杂度：O(nlogn)

核心思想

分治法（Divide and Conquer）

步骤（from wiki）：

采用分治法:

• 分割：递归地把当前序列平均分割成两半。

image.png

从上图可以看出，分割的步骤很像二叉树中的插入操作，因此时间复杂度为O(logN)。

• 合并：在保持元素顺序的同时将上一步得到的子序列集成到一起（归并）。

image.png

从上图可以看出，总共经过8次合并，最终得到一个完整的有序序列，即合并步骤的时间复杂度为O(N)

优点

稳定。时间复杂最好最坏都是O(nlogn)

代码思路：

1、mergeSort
以序列中间索引mid为分割点，拆分成左右两个序列，分别进行递归拆分&排序&合并

2、merge（核心代码）

• 申请一个临时数组temp；
• 第一次while循环，分别枚举并比较左右子序列的元素（左边由left开始，右边由mid + 1开始），将较小的元素依次存入temp数组中；
• 第二、第三个while循环是为了确保左右子序列所有元素都存入temp数组；
• 完成对temp数组的填充后，将temp数组元素copy至原来数组arr中，完成一次排序。

import java.util.Arrays;

public class MergeSort {

    public void mergeSort(int[] arr, int left, int right) {
        if (right <= left) return;
        int mid = (left + right) >> 1;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }

    private void merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int i = left, j = mid + 1, k = 0;
        while (i <= mid && j <= right) {
            temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
        }
        while (i <= mid) temp[k++] = arr[i++];
        while (j <= right) temp[k++] = arr[j++];
        System.arraycopy(temp, 0, arr, left, temp.length);

        // 或者下面方式
//        for (int p = 0; p < temp.length; p++) {
//            arr[left + p] = temp[p];// 易忽略的点： left+p
//        }

    }

    public static void main(String[] args) {
        int[] arr = {1,9,4,2,3,6,5};

        MergeSort mergeSort = new MergeSort();
        mergeSort.mergeSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

}