文章目录

1. 归并排序

1.1 算法思想

采用分治方法将原序列分治为logN个长度为2的子序列，然后排序并合并。核心是使得每个子序列有序，再使得子序列间有序。

1.2 算法步骤

  1. 把长度为n的输入序列分成两个长度为n/2的子序列；
  2. 对这两个子序列分别采用归并排序，即重复步骤1，2直至n等于1；
  3. 将两个排序好的子序列合并成一个最终的排序序列。

1.3 复杂度分析

因为分治算法基于选择算法，因此最好最坏情况的时间复杂度都是相同的。

最好时间复杂度 最坏时间复杂度 平均时间复杂度 空间复杂度
O(nlogn) O(nlogn) O(nlogn) O（n）

2. 代码实现

2.1 Java版

class Solution {
   
    public int[] sortArray(int[] nums) {
   
        // 归并排序
        // 选择排序的升级版，采用**分治方法**将原序列分治为logN个长度为2的子序列，然后排序并合并。
        // 时间onlgn，空间on，稳定
        int[] arr = new int[nums.length];
        int[] tmp = new int[nums.length];   // 临时数组
        System.arraycopy(nums,0,arr,0,nums.length);
        mergeSort(arr,0, arr.length-1,tmp);
        return arr;
    }
    private void mergeSort(int[] arr,int left, int right, int[] tmp){
   
        // 回溯
        if(left >= right) return;
        // 递归
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid,tmp);
        mergeSort(arr, mid+1, right,tmp);

        // 合并
        int l = left, r = mid +1;
        int tmpIdx = 0;
        while(l <= mid || r <= right){
   
            if(r > right || (l <= mid && arr[l] < arr[r])){
   
                tmp[tmpIdx++] = arr[l++];
            }else{
   
                tmp[tmpIdx++] = arr[r++];
            }
        }
        // 恢复
        for(int t = 0; t < tmpIdx; ++t){
   
            arr[left + t] = tmp[t];
        }
    }
}