题解 | 归并#排序#

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 将给定数组排序
     * @param arr int整型一维数组 待排序的数组
     * @return int整型一维数组
     */
    public int[] MySort (int[] arr) {
        // write code here
        process(arr, 0, arr.length - 1);
        return arr;
        
    }
    public void process(int[] arr, int L, int R) {
        if(R == L){
            return ;
        }
        int mid = L + ((R-L) >> 1);//计算中间点
        process(arr, L, mid);
        process(arr,mid+1, R);
        merge(arr, L, mid, R);
        

    }
    public  void merge(int[] arr, int L, int mid, int R){
        int[] help = new int[R - L +1];
        int i = 0;
        int p1 = L;
        int p2 = mid +1;
        while(p1 <= mid && p2 <= R){
            help[i++] = arr[p1] < arr[p2] ?arr[p1++]: arr[p2++];
        }
        while(p1 <= mid){
            help[i++] = arr[p1++];
        }
        while(p2 <= R){
            help[i++] = arr[p2++];
        }
        for(i = 0 ;i < help.length; i++){
            arr[L +i] = help[i];
        }
        
    }

}

原理分析：

这是一个无序数列：10、6、7、1、3、9、4、2。

首先是递的过程，一直二分拆解，直到拆分到最小时，在归的过程调用merge方法进行对比排序。

归过程如下步骤：

1. 申请一个空间来存放合并后的序列，大小为两个已经排序序列之和。
2. 设定两个指针，最初始位置分别为两个已经排序序列的起始位置。
3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一个位置。
4. 重复步骤3，直到某一指针超出序列尾，将另一序列剩下的所有元素直接复制到合并序列的列尾。

举个例子，如下图在归过程的开始为最小子问题10和6，申请两个空间，对比左边10和右边6，将小的6放进合并序列，同时右边指针到下个位置，超出列尾，则将左边所有元素直接复制到合并序列的列尾，而左边是有10，后面都是重复这个过程。