未捕获的RangeError。在p5.js中超过了最大调用堆栈大小。

Question

我试图在p5.js中运行mergesort算法，但发现 function mergesort(arr, start, end) 抛出了一个错误(超过了最大调用栈大小).输出应该是一个排序的数组，在浏览器窗口上以行的形式显示。

这是我的代码。

var values = []

function setup(){
    createCanvas(600,400);
    values.length = width;
    for(let i=0; i<values.length; i++){
        values[i] = random(height);
    }
    mergesort(values, 0, values.length-1)
}

function draw(){
    background(0);
    for (let i=0; i< values.length; i++){
        stroke(255,0,255);
        line(i, height, i, height - values[i]);
    }
}

function mergesort(arr, start, end){
    if(arr.length <= 1)
        return;

    let middle =arr.length/2

    mergesort(arr, start, middle);
    mergesort(arr, middle +1, end);
    merge(arr, start, middle, end);
}
function merge(arr, start, middle, end){
    let sizeL = middle - start;
    let sizeR = middle - end;
    let arrL = [];
    let arrR = [];
    for (let i = start; i < sizeL; i++) 
        arrL.push(arr[i])
    for (let j = sizeR; j < end; j++) 
        arrR.push(arr[j])
    let a = 0; 
    let b = 0;
    let k = 1;
    while (a< sizeL && b < sizeR){
        if (arrL[i] <= arrR[b]){
            arr[k] = arrL[a]; 
            a++; 
        } 
        else{
            arr[k] = arrR[b]; 
            b++; 
        } 
        k++; 
    } 
    while (a < sizeL){ 
        arr[k] = arrL[b]; 
        a++; 
        k++; 
    } 
    while (b < sizeR) { 
        arr[k] = arrR[b]; 
        b++; 
        k++; 
    }
}

请纠正这个错误

Answer 1

数组的长度永远不会改变，因此出现了以下情况 if(arr.length <= 1) 永无止境，结果 let middle = arr.length/2 总是一样的。

你必须评估是否 end - start <= 1 并计算 middel 由 (start + end)/2:

function mergesort(arr, start, end){
    if(end - start <= 0)
        return;

    let middle = Math.floor((start + end)/2);

    mergesort(arr, start, middle);
    mergesort(arr, middle+1, end);
    merge(arr, start, middle, end);
}

再有就是在索引编制上存在一些问题。注意，在 merge争论 start, middle, end 是指数。因此，数组的长度为 middle - start + 1 分别 end - middle. 而且你必须把排序后的元素从 start因此 k = start:

function merge(arr, start, middle, end){
    let sizeL = middle - start + 1;
    let arrL = [];
    for (let i = start; i < middle+1; i++) 
        arrL.push(arr[i])

    let sizeR = end - middle;
    let arrR = [];
    for (let j = middle+1; j < end+1; j++) 
        arrR.push(arr[j])

    let a = 0, b = 0, k = start;

    // [...]
}

可以通过以下方式简化代码 阵列 slice() 办法:

let arrL = arr.slice(start, middle+1);
let arrR = arr.slice(middle+1, end+1);

见例证。

var values = []

function setup(){
    createCanvas(600,400);
    values.length = width;
    for(let i=0; i<values.length; i++){
        values[i] = random(height);
    }
    mergesort(values, 0, values.length-1)
}

function draw(){
    background(0);
    for (let i=0; i< values.length; i++){
        stroke(255,0,255);
        line(i, height, i, height - values[i]);
    }
}

function mergesort(arr, start, end){
    if(end - start <= 0)
        return;

    let middle = Math.floor((start + end)/2);

    mergesort(arr, start, middle);
    mergesort(arr, middle+1, end);
    merge(arr, start, middle, end);
}

function merge(arr, start, middle, end){
    let sizeL = middle - start + 1;
    let arrL = arr.slice(start, middle+1);
    
    let sizeR = end - middle;
    let arrR = arr.slice(middle+1, end+1);
    
    let a = 0, b = 0, k = start;
    while (a< sizeL && b < sizeR){
        if (arrL[a] <= arrR[b]){
            arr[k++] = arrL[a++]; 
        } 
        else{
            arr[k++] = arrR[b++];  
        } 
    } 
    while (a < sizeL){ 
        arr[k++] = arrL[a++]; 
    } 
    while (b < sizeR) { 
        arr[k++] = arrR[b++]; 
    }
}

<script src="https://cdnjs.cloudflare.com/ajax/libs/p5.js/1.0.0/p5.min.js"></script>