Аннотация: Пузырьковая сортировка должна быть первым алгоритмом сортировки, который изучают большинство людей.У него простая идея и он является хорошим выбором для алгоритмов сортировки записей.Однако, поскольку его временная сложность составляет O(n^2), в дополнение к его изучению мы редко думают об этом вне времени и обычно упоминают больше алгоритмов сортировки с меньшей временной сложностью, таких как быстрая сортировка.Однако после улучшения классической пузырьковой сортировки, при определенных условиях вниз, все еще имеет место.

В этой статье сначала представлены три идеи по улучшению классической пузырьковой сортировки, а затем объединены эти три идеи для реализации метода, сочетающего в себе преимущества каждой из них.

Классическая реализация пузырьковой сортировки

Нет больше места для обсуждения идеи пузырьковой сортировки. Короче говоря, она помещает наибольшее значение в последнюю позицию массива путем сравнения и обмена попарно. Конкретная реализация может использовать двухслойный цикл, а внешний слой используется для управления внутренним слоем Позиция, в которой плавает наибольшее значение в цикле слоев, а внутренний слой используется для попарного сравнения и обмена позициями.

В качестве примера возьмем сортировку массива от меньшего к большему, по умолчанию для этого используются следующие части Классическая реализация пузырьковой сортировки выглядит следующим образом:

function bubbleSort(array){
    // 外层循环使用 end 来控制内层循环中极值最终上浮到的位置
    for(let end = array.length - 1; end > 0; end--){
        // 内层循环用来两两比较并交换
        for(let i = 0; i < end; i++){
            if(array[i] > array[i + 1]){
                swap(array, i, i+1);
            }
        }
    }
}

Функция, используемая в вышеуказанном кодеswap()Чтобы поменять местами элементы в двух позициях массива, эта функция будет использоваться в следующем коде следующим образом:

function swap(arr, i, j){
    // [arr[i],arr[i+1]] = [arr[i+1],arr[i]]; // ES6
    
    const temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

Улучшение 1: обработка случая, когда массив в целом уже отсортирован в процессе сортировки.

Если массив изначально упорядочен или был упорядочен в процессе сортировки, нет необходимости продолжать следующее сравнение, и массив можно вернуть напрямую, но классическая реализация пузырьковой сортировки все равно продолжит посещать каждый элемент по очереди. и сравните размер.Хотя в настоящее время есть только операции сравнения и нет операций подкачки, эти операции сравнения по-прежнему не нужны.

Признаком того, что массив уже упорядочен, является то, что во внутреннем цикле не происходит операции замены элементов (swap), то есть каждый элемент от начала до конца меньше элемента после него.

Используя описанный выше принцип, можно улучшить классическую реализацию: установить переменную для записи того, произошла ли операция обмена элементами в одном раунде внутреннего цикла, и определить, происходил ли обмен элементами после каждого раунда внутреннего цикла. происходит обмен элементами, массив упорядочивается и программа возвращается, иначе ничего не делать и запустить следующий цикл:

function bubbleSortOpt1(array){
    
    for(let end = array.length - 1; end > 0; end--){

        let isSorted = true; // <== 设置标志变量 isSorted 初始值为 true
        for(let i = 0; i < end; i++){
            if(array[i] > array[i + 1]){
                swap(array, i, i+1);

                isSorted = false;  // <== 发生了交换操作, 说明再这一轮中数组仍然无序, 将变量 isSorted 设置为 false
            }
        }

        // 在一轮内层循环后判断 是否有序, 若有序则直接 停止程序; 否则开始下一轮循环
        if(isSorted){  
            return ;  // <== 数组已经有序, 停止函数的执行
        }
    }
}

Идея улучшения 2: Массив локально упорядочен

Если массив локально упорядочен, т.е. массив после старта с определенной позиции уже упорядочен, то сравнивать эту часть массива нет необходимости.

В это время улучшенный метод: во время обхода можно отметить, что позиция события кроссовера произошла последним, рядом с внутренним контуром завершается это положение, вы можете сохранить дополнительную операцию сравнения.

Используйте переменную для хранения позиции, в которой произошла последняя операция подкачки, и установите ее в качестве конечной позиции следующего внутреннего цикла:

function bubbleSortOpt2(array){
    let endPos = array.length - 1; // 记录这一轮循环最后一次发生交换操作的位置

    while(endPos > 0){
        let thisTurnEndPos = endPos; // <== 设置这一轮循环结束的位置

        for(let i = 0; i < thisTurnEndPos; i++){
            if(array[i] > array[i+1]){
                swap(array, i, i+1);

                endPos = i; // <== 设置(更新)最后一次发生了交换操作的位置
            }
        }
        
        // 若这一轮没有发生交换,则证明数组已经有序,直接返回即可
        if(endPos === thisTurnEndPos){ 
	        return ;
	    }
    }
}

Идея улучшения третья: вернуть максимальное и минимальное значения одновременно

В классической реализации наибольшее значение каждый раз подгоняется к концу текущего массива, а наименьшее значение не обрабатывается.На самом деле, в одном и том же раунде внешних циклов наибольшее значение может подгоняться к концу текущего массива. массив в то же время и наименьшее значение может быть скорректировано.Минимальное значение корректируется вперед, пока максимальное значение расположено спереди назад во внутреннем цикле, и положение этих минимальных значений также Двунаправленная пузырьковая сортировка.

Он более абстрактный, и его легче понять, взглянув на код:

// 双向冒泡排序, 不仅把最大的放到最后, 同时把最小的放到最前
function bubbleSortOpt3(array){
    // <== 设置每一轮循环的开始与结束位置
    let start = 0, 
        end = array.length - 1;

    while(start < end){
        for(let i = start; i < end; i++){ // 从start位置end位置过一遍安排最大值的位置
            if(array[i] > array[i+1]){
                swap(array, i, i+1);
            }
        }
        end --; // <== 由于当前最大的数已经放到了 end 位置, 故 end 位置向前移动

        for(let i = end; i > start; i--){ // 从end向start位置过一遍, 安排最小值的位置
            if(array[i] < array[i-1]){
                swap(array, i, i-1);
            }
        }
        start ++; // <== 由于当前最小的数已经放到了 start 位置, 故 start 位置向后移动
    } 
}

Однако этот метод также имеет тот недостаток, что он перемещается вперед и назад на одну позицию за раз, т. е.end--а такжеstart++.. не может справиться с двумя случаями, упомянутыми в предыдущем разделе, поэтому эти три метода можно комбинировать, чтобы получить соответствующие преимущества.

Сочетание трех идей

Вышеупомянутые три идеи касаются ситуации, в которой весь массив уже в порядке, локальный массив в порядке, а максимальное и минимальное значения помещаются в соответствующие позиции в процессе сортировки.Тогда преимущества трех вышеуказанных можно комбинировать для достижения лучших результатов.

Шаг за шагом, давайте поговорим о сочетании двух идей

Сочетание идей 1 и 2

Сочетание идей 1 и 2 для обработки случая, когда массив частично упорядочен, а в целом заказано во время процесса сортировки:

function bubbleSortOpt1and2(array){
    let endPos = array.length - 1; // 记录下一轮循环结束的位置, 也就是上一轮最后交换的位置

    while(endPos > 0){
        let isSorted = true; // 设置数组整体有序标志变量
        let thisTurnEndPos = endPos; // 记录这一轮循环结束的位置

        for(let i = 0; i < thisTurnEndPos; i++){
            if(array[i] > array[i+1]){
                swap(array, i, i+1);

                endPos = i; // 这个位置发生了交换, 将这个位置记录下来
                isSorted = false;  // 设置本轮为无序
            }
        }

        if(isSorted){ // 判断数组是否已经整体有序
            console.log(endPos);
            return;
        }
    }
}

Сочетание идей 2 и 3

Объединение идей 2 и 3 для одновременной обработки максимального и минимального значений с обоих направлений и решения случая, когда массив локально упорядочен

// 结合第2、3种改进方式的思想, 记录双向排序中每个方向的最后交换位置, 并更新下一轮循环的结束位置
function bubbleSortOpt2and3(array){
    let start = 0, startPos = start,
        end = array.length - 1, endPos = end;

    while(start < end){
        
        // 从前向后过一遍
        for(let i = start; i < end; i++){ 
            if(array[i] > array[i+1]){
                swap(array, i, i+1);
                endPos = i; // 记录这个交换位置
            }
        }
        end = endPos;  // 设置下一轮的遍历终点

        // 从后向前过一遍
        for(let i = end; i > start; i--){ 
            if(array[i] < array[i-1]){
                swap(array, i, i-1);
                startPos = i; // 记录这个交换位置
            }
        }
        start = startPos; // 设置下一轮的遍历终点

    }
}

Используйте все три идеи одновременно

После того, как у вас есть основа для объединения двух и двух, несложно написать код, сочетающий эти три идеи:

function bubbleSortOptTriple(array){
    let start = 0, startPos = start,
        end = array.length - 1, endPos = end;

    while(start < end){
        let isSorted = true; // 设置有序无序的标志变量
        // 从前向后过一遍
        for(let i = start; i < end; i++){ 
            if(array[i] > array[i+1]){
                swap(array, i, i+1);

                endPos = i; // 记录这个交换位置
                isSorted = false; // 设置无序标志
            }
        }

        if(isSorted){
            return;
        }

        end = endPos;  // 设置下一轮的遍历终点
        

        // 从后向前过一遍
        for(let i = end; i > start; i--){ 
            if(array[i] < array[i-1]){
                swap(array, i, i-1);

                startPos = i; // 记录这个交换位置
                isSorted = false; // 设置无序标志
            }
        }

        if(isSorted){
            return;
        }

        start = startPos; // 设置下一轮的遍历终点
    }
}

Это конец?

На самом деле, приведенная выше программа все еще может быть улучшена: нам не нужен другой набор переменных в массиве для записи, был ли поездка отсортирована порядок, но можно сравнить после окончания циклаendPosРавноend, если равно, значит в этом раунде нет матчаendPosUpdate, то есть операции подкачки не происходит, что еще раз указывает на то, что массив уже в порядке.startPosа такжеstartТо же самое справедливо.