三谈归并排序（含尾递归）

摘要：一谈，原始的归并排序二谈，优化后的归并排序优化算法的指导思想之一，找到某些可以简化处理的特殊情况合并时的特殊情况当的最后一个元素小于的第一个元素时，那么顺序就应该是当的最后一个元素小于的第一个元素时，那么顺序就应该是所以修改函数如下适时

function mergeSort(arr) {
    let {
        length
    } = arr
    if (length < 2) {
        return arr
    }
    let midIndex = Math.floor(length / 2)
    let leftArr = mergeSort(arr.slice(0, midIndex))
    let rightArr = mergeSort(arr.slice(midIndex))
    return merge(leftArr, rightArr)
}

function merge(leftArr, rightArr) {
    let i = 0,
        j = 0,
        arr = []
    while (true) {
        if (i === leftArr.length) {
            arr.push(...rightArr.slice(j))
            break
        }
        if (j === rightArr.length) {
            arr.push(...leftArr.slice(i))
            break
        }
        if (leftArr[i] < rightArr[j]) {
            arr.push(leftArr[i])
            i++
        }
        if (rightArr[j] <= leftArr[i]) {
            arr.push(rightArr[j])
            j++
        }
    }
    return arr
}

let arr = [1, 5, 2, 11, 7, 3, 1, 6, 17, 10]
let arrInOrder = mergeSort(arr)
console.log(arrInOrder) // [ 1, 1, 2, 3, 5, 6, 7, 10, 11, 17 ]

优化算法的指导思想之一，找到某些可以简化处理的特殊情况

当 leftArr 的最后一个元素小于 rightArr 的第一个元素时，那么顺序就应该是 [leftArr, rightArr]

当 rightArr 的最后一个元素小于 leftArr 的第一个元素时，那么顺序就应该是 [rightArr, leftArr]

所以修改 mergeSort 函数如下

function mergeSort(arr) {
    let {
        length
    } = arr
    if (length < 2) {
        return arr
    }
    let midIndex = Math.floor(length / 2)
    let leftArr = mergeSort(arr.slice(0, midIndex))
    let rightArr = mergeSort(arr.slice(midIndex))
    if (leftArr[leftArr.length - 1] <= rightArr[0]) {
        return [...leftArr, ...rightArr]
    }
    if (rightArr[rightArr.length - 1] <= leftArr[0]) {
        return [...rightArr, ...leftArr]
    }
    return merge(leftArr, rightArr)
}
...

当数组的长度变小到一定程序时，采用插入排序

先修改代码如下

function mergeSort(arr, fromIndex, length) {
    if (length < 2) {
        return
    }
    mergeSort(arr, fromIndex, Math.floor(length / 2))
    mergeSort(arr, fromIndex + Math.floor(length / 2), length - Math.floor(length / 2))
    merge(arr, fromIndex, length)
}

function merge(arr, fromIndex, length) {
    let leftArr = arr.slice(fromIndex, fromIndex + Math.floor(length / 2))
    let rightArr = arr.slice(fromIndex + Math.floor(length / 2), fromIndex + length)
    let i = 0,
        j = 0,
        orderedArr = []
    while (true) {
        if (i === leftArr.length) {
            orderedArr.push(...rightArr.slice(j))
            break
        }
        if (j === rightArr.length) {
            orderedArr.push(...leftArr.slice(i))
            break
        }
        if (leftArr[i] < rightArr[j]) {
            orderedArr.push(leftArr[i])
            i++
        }
        if (rightArr[j] <= leftArr[i]) {
            orderedArr.push(rightArr[j])
            j++
        }
    }
    arr.splice(fromIndex, length, ...orderedArr)
}

let arr = [1, 5, 2, 11, 7, 3, 1, 6, 17, 10]
mergeSort(arr, 0, arr.length)
arr // [ 1, 1, 2, 3, 5, 6, 7, 10, 11, 17 ]

把传过的参数都记录下来，存在 argsArr 中

例如在计算 fromIndex 为 0， length 为 10 时，分为三步

先要通过mergeSort计算 fromIndex 为 0， length 为 5

再通过mergeSort计算 fromIndex 为 5， length 为 5

最后merge (arr, 0, 10)

由于尾递归调用，只能先计算 mergeSort(arr, 0, 5, argsArr)

而把 [0, 10, 5, 5] 存起来，前两个参数是merge的参数，后两个是mergeSort的参数

用过的参数就把它去掉，所以[0, 10, 5, 5] => [0, 10] =>

function mergeSort(arr, fromIndex, length, argsArr) {
    if (length < 2) {
        let args = argsArr.pop()
        while (args) {
            if (args.length === 4) {
                argsArr.push([args[0], args[1]])
                break
            }
            if (args.length === 2) {
                merge(arr, args[0], args[1])
                args = argsArr.pop()
            }
        }
        if (args) {
            return mergeSort(arr, args[2], args[3], argsArr)
        } else {
            return
        }
    }
    argsArr.push([fromIndex, length, fromIndex + Math.floor(length / 2), length - Math.floor(length / 2)])
    return mergeSort(arr, fromIndex, Math.floor(length / 2), argsArr)
}

function merge(arr, fromIndex, length) {
    let leftArr = arr.slice(fromIndex, fromIndex + Math.floor(length / 2))
    let rightArr = arr.slice(fromIndex + Math.floor(length / 2), fromIndex + length)
    let i = 0,
        j = 0,
        orderedArr = []
    while (true) {
        if (i === leftArr.length) {
            orderedArr.push(...rightArr.slice(j))
            break
        }
        if (j === rightArr.length) {
            orderedArr.push(...leftArr.slice(i))
            break
        }
        if (leftArr[i] < rightArr[j]) {
            orderedArr.push(leftArr[i])
            i++
        }
        if (rightArr[j] <= leftArr[i]) {
            orderedArr.push(rightArr[j])
            j++
        }
    }
    arr.splice(fromIndex, length, ...orderedArr)
}

let arr = [1, 5, 2, 11, 7, 3, 1, 6, 17, 10, 312, 312, 1, 1, 2323, 4, 56, 3, 14, 5543]
mergeSort(arr, 0, arr.length, [])
console.log(arr)

其中 merge 函数不变，修改 mergeSort 函数

function mergeSort(arr) {
    for (let size = 1; size < arr.length; size = size * 2) {
        for (let i = 0; i + size < arr.length; i = i + size * 2) {
            merge(arr, i, size * 2)
        }
    }
}
function merge(arr, fromIndex, length) {
  ...
}