Блог

Главная - Вопросы по программированию - Бесконечный цикл при построении сортировки слиянием в JavaScript

Бесконечный цикл при построении сортировки слиянием в JavaScript

#javascript #mergesort

#javascript #сортировка слиянием

Вопрос:

Я пытаюсь создать исправленную версию, но каждый раз сталкиваюсь с ошибками. mergeSort Я несколько раз запускал debugger, и похоже, что все сортируется правильно до последнего шага, на котором я перехожу к строке в loader.js досье.

Кто-нибудь может помочь мне проверить это? Заранее спасибо!

 
Array.prototype.mergeSort = function(callback) {
    if (this.length <= 1) return this;

    if (!callback) {
        callback = function(x, y) {
            if (x > y) return -1;
            else if (x < y) return 1;
            else return 0;
        };
    }

    const mid = Math.floor(this.length / 2);
    const sortedLeft = this.slice(0, mid).mergeSort(callback);
    const sortedRight = this.slice(mid).mergeSort(callback);

    return sortedLeft.merge(sortedRight, callback);
};

Array.prototype.merge = function(arr, callback) {
    let merged = [];

    while (this.length > 0 || arr.length > 0) {
        if (callback(this[0], arr[0]) < 0) {
            merged.push(arr.shift());
            break;
        } else if (callback(this[0], arr[0]) >= 0) {
            merged.push(this.shift());
            break;
        }
    }

    merged = merged.concat(this);
    merged = merged.concat(arr);

    return merged;
};

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

1. Примечание стороны; ваша первая callback = ... часть фактически такая же, как return y - x;

2. Второе примечание; } else if (callback(this[0], arr[0]) >= 0) { это просто оператор else в паре с первым if .

3. Понял по обоим пунктам, немного почистил его, но по какой-то причине все еще возникают проблемы.

4. @Taplar: не совсем, например return y - x , не обрабатывает строки, тогда как функция сравнения OP по умолчанию выполняет.

5. @chqrlie если значения являются строковыми, вычитание в первую очередь не подходит, и вместо этого следует использовать собственный localeCompare .

Ответ №1:

Цикл слияния должен останавливаться, когда любой из списков пуст: вместо while (this.length > 0 || arr.length > 0) того, чтобы вы должны написать:

 while (this.length > 0 amp;amp; arr.length > 0)

Кроме того, вы не должны break переходить из цикла после каждого сохранения в merge массив, и излишне сравнивать элементы дважды.

Вот исправленная версия:

 Array.prototype.merge = function(arr, callback) {
    let merged = [];

    while (this.length > 0 amp;amp; arr.length > 0) {
        if (callback(this[0], arr[0]) < 0) {
            merged.push(arr.shift());
        } else {
            merged.push(this.shift());
        }
    }
    merged = merged.concat(this);
    return merged.concat(arr);
};

Однако обратите внимание, что ваш merge метод сортирует массив в порядке убывания, а callback функция по умолчанию также сравнивает элементы в порядке убывания, в результате чего массив сортируется в порядке возрастания по совпадению. Возможно, вы захотите упростить это и принять null функцию обратного merge вызова.

Вот более общая версия:

 Array.prototype.mergeSort = function(callback) {
    if (this.length <= 1)
        return this;

    const mid = this.length >> 1;
    const sortedLeft = this.slice(0, mid).mergeSort(callback);
    const sortedRight = this.slice(mid).mergeSort(callback);

    return sortedLeft.merge(sortedRight, callback);
};

Array.prototype.merge = function(arr, callback) {
    let merged = [];

    if (callback) {
        while (this.length > 0 amp;amp; arr.length > 0) {
            if (callback(this[0], arr[0]) <= 0) {
                merged.push(this.shift());
            } else {
                merged.push(arr.shift());
            }
        }
    } else {
        while (this.length > 0 amp;amp; arr.length > 0) {
            if (this[0] <= arr[0]) {
                merged.push(this.shift());
            } else {
                merged.push(arr.shift());
            }
        }
    }
    return merged.concat(this).concat(arr);
};
Метки: