排序算法-归并排序

复杂度

时间复杂度(平均) 时间复杂度(最好) 时间复杂度(最坏) 空间复杂度 稳定性 复杂性
O(nlog2n) O(nlog2n) O(nlog2n) O(n) 稳定 较复杂

思路

  1. 采用分治思想,先"分"再"治"
  2. 分的过程即将数组分成若干个子部分,子部分最少数组元素为1
  3. 治的过程即将子部分进行合并,两两合并到一组
  4. 最终治到一组时排序结束

代码:

 public int[] mergeSort_1(int[] nums, int l, int r){

    if(l == r) return new int[]{nums[l]};//当分到子数组元素个数为1时返回该元素数组

    int mid = (l + r) / 2;

    int[] lArr = mergeSort_1(nums, l, mid);//左分
    int[] rArr = mergeSort_1(nums, mid + 1, r);//右分
    int[] merge = new int[r - l + 1];//合治数组

    //合治 i,j,k分别处理lArr,rArr与merge的下标
    int i = 0, j = 0, k = 0;
    while(i < lArr.length && j < rArr.length){
        if(lArr[i] < rArr[j]) merge[k++] = lArr[i++];
        else merge[k++] = rArr[j++];
    }
    while(i < lArr.length){
        merge[k++] = lArr[i++];
    }
    while(j < rArr.length){
        merge[k++] = rArr[j++];
    }
    return merge;
}
上一篇:[LeetCode] 23. Merge k Sorted Lists


下一篇:git使用merge合并代码没有生效,提示already up to date