时间戳

首页 > 解决方案 > 为什么此合并排序代码在 python 中有效，但在 javascript 中无效

javascript - 为什么此合并排序代码在 python 中有效，但在 javascript 中无效

问题描述

有谁知道为什么这段代码不起作用，我在 python 中尝试了相同的代码，它运行良好。

function merge(l, m, r) {
    let divider = m + 1
    let l_cache = l
    let out_list = []
    for (let i = 0; i < r - l + 1; i++) {
        if (l > m) {
            out_list.push(numbers[divider])
            divider += 1
        } else if (divider > r) {
            out_list.push(numbers[l])
            l += 1
        } else if (numbers[l] < numbers[divider]) {
            out_list.push(numbers[l])
            l += 1
        } else if (numbers[l] >= numbers[divider]) {
            out_list.push(numbers[divider])
            divider += 1
        }
    }
    for (let i = 0; i < out_list.length; i++) {
        numbers[i + l_cache] = out_list[i]
    }
}

function MergeSort(l, r) {
    if (l < r) {
        let m = Math.floor((l + r - 1) / 2)
        MergeSort(l, m)
        MergeSort(m + 1, r)
        merge(l, m, r)
    }
}

var numbers = [ 42, 60, 33, 79, 15, 0, 88, 62, 27, 46 ]
MergeSort(0, numbers.length - 1)

输入：[42, 60, 33, 79, 15, 0, 88, 62, 27, 46]

输出：[0, 15, 27, 33, 42, 46, 60, 46, 62 ,62]

预期输出：[0, 15, 27, 33, 42, 46, 60, 62, 79, 88]

标签： javascriptsortingmergesort

解决方案

问题是你l在循环体中发生了变异，但仍然在你的条件中使用它for (let i = 0; i < r-l+1; i++)。这样合并就过早结束并且out_list不包含它应该包含的所有内容。通过使用解决此问题

for (let i = 0; i < r-l_cache+1; i++) {
//                    ^^^^^^^

在 python 中，您可能使用了range()仅评估一次并保持其停止值的 a。

或者，您可能不想依赖算术来预先确定迭代次数，而是使用结束条件

while (l <= m || divider <= r) {

推荐阅读