js学习笔记之排序算法的原理及代码

归并排序：

把数组从中间拆分成左右两部分，然后把左右两部分再拆分，直到拆分的数组中只有一个元素。

拆分完后再将拆分的数组依次合并成有序数组，合并到最后会变成左右两个有序数组的合并。具体代码如下

const merge = (left, right) => {
    const result = []
    let il = 0
    let ir = 0
    while(il < left.length && ir < right.length) {
        if(left[il] < right[ir]) {
            result.push(left[il++]) // 这里的left[il++]是先进行取值运算left[il], 在进行自增运算il++
        } else {
            result.push(right[ir++])
        }
    }
    while (il < left.length) {
        result.push(left[il++])
    }
    while (ir < right.length) {
        result.push(right[ir++])
    }
    return result
}
const mergeSortRec = array => {
    if (array.length === 1) {
        return array
    }
    const mid = Math.floor(array.length / 2)
    const left = array.slice(0, mid)
    const right = array.slice(mid, array.length)
    return merge(mergeSortRec(left), mergeSortRec(right))
}

let arr = [5, 3, 2, 4, 1]
console.log(mergeSortRec(arr))