归并排序

[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
};