javascript - javascript中的快速排序算法中的“超出最大调用堆栈大小”

Question

我目前正在研究一些排序算法，但我被我的快速排序算法卡住了。

确切的错误：

quicksort.js:25 Uncaught RangeError: 在快速排序 (quicksort.js:25) 在快速排序 (quicksort.js:27) 在快速排序 (quicksort.js:27) 在快速排序 (quicksort.js:27) 在快速排序 (quicksort.js:27) 快速排序 (quicksort.js:27) 快速排序 (quicksort.js:27) 快速排序 (quicksort.js:27) 快速排序 (quicksort.js:27) 快速排序 (quicksort.js :27)

代码：

function quicksort(array, left, right) {
    if (array.length > 1) {
        let sort = quicksortChange(array, left, right); //line 25
        if (left < sort - 1) {
            quicksort(array, left, sort - 1); //line 27
        }
        if (right > sort) {
            quicksort(array, sort, right);
        }
    }
    return array;
}


function quicksortChange(array, left, right) {
    let pivot_number = Math.floor(array.length / 2);
    let pivot = array[pivot_number];
    for (i = 0; i < pivot_number; i++) {
        if (array[i] > pivot) {
            let a = array[i];
            for (j = array.length - 1; j > pivot; j--) {
                if (array[j] < pivot) {
                    let b = array[j];
                    if (a <= b) {
                        array[i] = b;
                        array[j] = a;
                        i++
                        j--
                    }
                }
            }
        }
    }
    return i;
}

你开始算法：

let cleanArray = quicksort(array, 0, array.length - 1)

标签： javascriptarraysperformancesortingquicksort

Answer 1

使用经典 Hoare 分区算法的快速排序示例：

function quicksort(array, left, right) {
    if(left >= right)
        return;
    var pivot = array[Math.floor((left + right) / 2)];
    var i = left - 1;
    var j = right + 1;
    while (true){
            while (array[++i] < pivot);
            while (array[--j] > pivot);
            if (i >= j)
                break;
            var t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
    quicksort(a, left, j);
    quicksort(a, j+1, right);
}

var a = new Array(1000)
for (var i = 0; i < a.length; i++) {
    a[i] = parseInt(Math.random() * 1000000000)
}
console.time('measure')
quicksort(a, 0, a.length-1)
console.timeEnd('measure')
for (var i = 1; i < a.length; i++) {
    if(a[i-1] > a[i]){
        console.log('error')
        break
    }
}