javascript - javascript中的合并排序返回重复的元素

Question

我正在尝试在 JS 中进行合并排序，但不明白我哪里搞砸了。我希望它返回 [1,2,3,4]，它返回 [1,1,1,4]。

它的哪一部分需要改变？

var array = [3,2,1,4]

function mergeSort(array) {
    if (array.length === 1) {
        return array
    } else {
        mid = Math.floor(array.length/2)
        left = mergeSort(array.slice(0, mid))
        right = mergeSort(array.slice(mid, array.length))
        return merge(left, right)
    }
}

function merge(left, right) {
    var leftIndex = 0
    var rightIndex = 0
    var sorted = []

    while (leftIndex < left.length && rightIndex < right.length) {
        if (left[leftIndex] <= right[rightIndex]) {
            sorted.push(left[leftIndex])
            leftIndex += 1
        } else {
            sorted.push(right[rightIndex])
            rightIndex += 1
        }
    }

    if (leftIndex < left.length) {
        sorted = sorted.concat(left.slice(leftIndex))
    } else if (rightIndex < right.length) {
        sorted = sorted.concat(right.slice(rightIndex))
    }
    return sorted
}

console.log(mergeSort(array))

Answer 1

您遇到了范围界定问题。您尚未声明 left、right 和 mid 变量，因此它们被视为隐式全局变量并导致困惑。

固定:

function mergeSort(array) {
    if (array.length === 1) {
        return array
    } else {
        var mid = Math.floor(array.length/2)
        var left = mergeSort(array.slice(0, mid))
        var right = mergeSort(array.slice(mid, array.length))
        return merge(left, right)
    }
}