Блог

Главная - Вопросы по программированию - «Превышен максимальный размер стека вызовов» при использовании алгоритма быстрой сортировки в javascript

«Превышен максимальный размер стека вызовов» при использовании алгоритма быстрой сортировки в javascript

#javascript #arrays #performance #sorting #quicksort

Вопрос:

В настоящее время я работаю над некоторыми алгоритмами сортировки, но я застрял в своем алгоритме быстрой сортировки.

Точная ошибка:

быстрая сортировка.js:25 Ошибка в диапазоне: Превышен максимальный размер стека вызовов при быстрой сортировке (быстрая сортировка.js:25) при быстрой сортировке (быстрая сортировка.js:27) при быстрой сортировке (быстрая сортировка.js:27) при быстрой сортировке (быстрая сортировка.js:27) при быстрой сортировке (быстрая сортировка.js:27) при быстрой сортировке (быстрая сортировка.js:27) при быстрой сортировке (быстрая сортировка.js:27) при быстрой сортировке (быстрая сортировка.js:27) при быстрой сортировке (быстрая сортировка.js:27) при быстрой сортировке (быстрая сортировка.js:27)при быстрой сортировке (быстрая сортировка.. js: 27) при быстрой сортировке (быстрая сортировка. js: 27) при быстрой сортировке (быстрая сортировка. 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)

Комментарии:

1. Каково конечное условие? Я вижу только проверку массива, в котором нет элементов, но массив, похоже, прошел без изменений?

2. вы всегда передаете один и тот же массив, поэтому array.length он никогда не уменьшится, и у вас бесконечная рекурсия ..

3. quicksortChange похоже, что он не использует свои left right параметры или.

4. @RaymondChen Да, я понимаю. Моя вина. Но есть все та же проблема. Есть идеи, как я могу решить проблему с рекурсией?

5. Используйте параметры left и right для управления разделом. Прямо сейчас вы разделяете весь массив, поэтому каждая рекурсия просто начинает проблему с нуля, и вы никогда не заканчиваете.

Ответ №1:

Пример быстрой сортировки с использованием классического алгоритма секционирования Хоара:

 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
    }
}
Метки: