Uncaught RangeError: Maximum call stack size exceeded in p5.js

Question

我正在尝试运行 p5.js 中的合并排序算法，但 function mergesort(arr, start, end) 抛出错误（超出最大调用堆栈大小）。输出应该是在浏览器上显示为行的排序数组 window.

这是我的代码：

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 并通过 (start + end)/2 计算 middel:

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;

    // [...]
}

可以使用Array slice() method简化代码：

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>

Uncaught RangeError: Maximum call stack size exceeded in p5.js

Uncaught RangeError: Maximum call stack size exceeded in p5.js

javascript

processing

p5.js