摘要：一談，原始的歸并排序二談，優(yōu)化后的歸并排序優(yōu)化算法的指導(dǎo)思想之一，找到某些可以簡(jiǎn)化處理的特殊情況合并時(shí)的特殊情況當(dāng)?shù)淖詈笠粋€(gè)元素小于的第一個(gè)元素時(shí)，那么順序就應(yīng)該是當(dāng)?shù)淖詈笠粋€(gè)元素小于的第一個(gè)元素時(shí)，那么順序就應(yīng)該是所以修改函數(shù)如下適時(shí)

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 ]

優(yōu)化算法的指導(dǎo)思想之一，找到某些可以簡(jiǎn)化處理的特殊情況

當(dāng) leftArr 的最后一個(gè)元素小于 rightArr 的第一個(gè)元素時(shí)，那么順序就應(yīng)該是 [leftArr, rightArr]

當(dāng) rightArr 的最后一個(gè)元素小于 leftArr 的第一個(gè)元素時(shí)，那么順序就應(yīng)該是 [rightArr, leftArr]

所以修改 mergeSort 函數(shù)如下

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)
}
...

當(dāng)數(shù)組的長(zhǎng)度變小到一定程序時(shí)，采用插入排序

先修改代碼如下

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 ]

把傳過的參數(shù)都記錄下來，存在 argsArr 中

例如在計(jì)算 fromIndex 為 0， length 為 10 時(shí)，分為三步

先要通過mergeSort計(jì)算 fromIndex 為 0， length 為 5

再通過mergeSort計(jì)算 fromIndex 為 5， length 為 5

最后merge (arr, 0, 10)

由于尾遞歸調(diào)用，只能先計(jì)算 mergeSort(arr, 0, 5, argsArr)

而把 [0, 10, 5, 5] 存起來，前兩個(gè)參數(shù)是merge的參數(shù)，后兩個(gè)是mergeSort的參數(shù)

用過的參數(shù)就把它去掉，所以[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 函數(shù)不變，修改 mergeSort 函數(shù)

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) {
  ...
}