归并排序

[Betty985]

思想

• 将序列中待排序数组中每个数字分为一组
• 将若干组两两合并，并保证合并后的组是有序的
• 重复第二步操作直到只剩下一组，排序完成

  递归

  function mergeSort(arr){
  // 自上而下
  let len=arr.length
  // 终止条件
  if(len<2){
      return arr
  }
  let middle=Math.floor(len/2)
  let left=arr.slice(0,middle)
  let right=arr.slice(middle)
  return merge(mergeSort(left),mergeSort(right))
  }
  function merge(left,right){
  let result=[]
  while(left.length&&right.length){
      // =  保证排序稳定
      if(left[0]<=right[0]){
          result.push(left.shift())
      }else{
          result.push(right.shift())
      }
  }
  while(left.length) result.push(left.shift())
  while(right.length) result.push(right.shift())
  return result
  }

  分析

  归并排序不是原地排序算法

  归并排序是一种稳定的排序算法

  归并排序的时间复杂度是O(nlogn),空间复杂度是O(n)

[Betty985]

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function(nums) {
// 归并排序（二叉树的后序遍历）
function sort(nums,l,h){
    if(l==h){
        return
    }
    let mid=l+Math.floor((h-l)/2)
    sort(nums,l,mid)
    sort(nums,mid+1,h)
    merge(nums,l,mid,h)
}
function merge(nums,l,mid,h){
    let tmp=[]
    for (let i = l; i <= h; i++) {
        tmp[i] = nums[i];
    }
    let i=l,j=mid+1
    for(let p=l;p<=h;p++){
        if(i==mid+1){
            // 左边数组合并完成
            nums[p]=tmp[j++]
        }else if(j==h+1){
            // 右边数组合并完成
            nums[p]=tmp[i++]
        }else if(tmp[i]<=tmp[j]){
            nums[p]=tmp[i++]
        }else{
            nums[p]=tmp[j++]
        }
    }
}
sort(nums,0,nums.length-1)
return nums
};