[数据结构与算法]常见排序之归并排序（JAVA实现）

常见排序

归并排序

算法介绍：O(nlogn)

归并排序是分治思想的最典型的例子

分别通过递归调用将他们单独排序，最后将有序的子数组归并为最终的排序结果。该递归的出口在于如果

一个数组不能再被分为两个子数组，那么就会执行merge进行归并，在归并的时候判断元素的大小进行排序。

归并排序需要申请额外的数组空间，导致空间复杂度提升，是典型的以空间换时间的操作。

思路概况：

归并操作的工作原理如下：

第一步：申请空间，使其大小为数组大小，该空间用来存放合并后的序列

第三步：递归进行拆分直到元素个数为1

第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置

第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，移动指针到下一位置并继续比较

代码：

class Solution {
    public int[] sortArray(int[] nums) {
    int[] temp = new int[nums.length];//开辟辅助数组
      merge(nums,0,nums.length-1,temp);
      return nums;
    }
  
    public void merge(int[] nums,int left,int right,int[] temp){
        if(left == right){
            return;
        }
        int mid = (left+right)>>>1;
         //递归拆分数组
        merge(nums,left,mid,temp);
        merge(nums,mid+1,right,temp);
        //递归归并数组
        mergeSort(nums,left,mid,right,temp);
    }
    //合并数组函数
    public void mergeSort(int[] nums,int left,int M,int right,int[] temp){
        //将数组以中心M分为左半边和右半边
            int l = left;
            int m = M;
            int r = m+1;
    //这里的k必须也是从left下标开始。因为所需要排序的下标是left-right,排完存入temp数组中
            int k =left;
        
      //在左半区left-mid之间和右半区mid+1-right之间比较出较小的插入到temp数组的（left-right位置）
            while(l<=M&&r<=right){
                if(nums[l] < nums[r]){
                    //如果在左半区找出较小的则继续移动左半区
                    temp[k++] = nums[l++]; 
                }else{
                    temp[k++] = nums[r++];
                }
            }
        //由于左右半区的大小其实是随机的，所以会出现右半区或左半区全部加入temp而另一半区还有数据较大的没加进来
            while(l<=M){
                temp[k] =nums[l];
                k++;
                l++;
            }
            while(r<=right){
                temp[k++] = nums[r++];
            }
            for(int i=left ;i<=right;i++){
                nums[i]=temp[i];
            }
        }
}