javascript - 在javascript中合并排序

Question

我正在学习算法简介并将伪代码翻译成各种语言以供练习。

我卡在 javascript 上了。我无法弄清楚为什么我的合并功能失败并重复输入。你知道为什么吗？

谢谢

function mergesort(a){
    if (a.length <=1) {
        return a;
        }
    mid = Math.round((a.length/2));
    left = a.slice(0, mid);
    right = a.slice(mid);
    console.log(left,right);
    return merge(mergesort(left), mergesort(right));
}

function merge(left, right) {
    sorted = [];
    console.log(sorted,left, right, left[0], right[0]);
    while (left && left.length >0 && right && right.length >0){
        if (left[0] <= right[0]) {
            sorted.push(left.shift());
            console.log("left", left, right);
        }
        else {
            sorted.push(right.shift());
            console.log("left", left, right);
        }
    }
    return sorted.concat(left,right);
}


a = [234,526,6,3,2,5];
mergesort(a);

Answer 1

您的算法看起来不错，最大的问题是您正在创建全局变量。当您在不使用 var 关键字的情况下创建变量时，该变量将成为全局变量。

在您的情况下，第一次创建全局变量然后在连续的递归调用中，您不是在创建新变量，而是重新分配给相同的全局变量。要解决此问题，只需在变量声明前加上 var 前缀，如下所示

var mid = Math.round((a.length/2));
var left = a.slice(0, mid);
var right = a.slice(mid);
...
...
...
var sorted = [];

有了这个改变，结果就变成了

[ 2, 3, 5, 6, 234, 526 ]