[Изучите алгоритм сортировки вместе] 2 Пузырьковая сортировка

задняя часть алгоритм GitHub JavaScript

Пузырьковая сортировка

Список статей из этой серии и соответствующие описания см.[Изучайте алгоритмы сортировки вместе] 0 Предисловие
Вы также можете перейти непосредственно кgithubОзнакомьтесь с полной статьей и исходным кодом здесь!

принцип

Первый взглядWikipediaОпределение:

Bubble sort is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.

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

значок

Это можно понять с помощью демонстрации анимации, следующих двух анимаций, найденных в Интернете. Если вы хотите манипулировать различными параметрами для демонстрации, вы можете перейти на этот сайтvisualgo.netПопробуйте.

图示1

图示2

Код

Что касается кода, код в README содержит только функции, реализующие алгоритм.Чтобы узнать конкретный работающий код, проверьте файлы в этом каталоге.

начальное пузырение

Код выглядит следующим образом, см.bubble_sort_1.js.

const bubbleSort = (array) => {
    // 不修改原数组
    const originValues = array.slice(); 

    // 迭代次数 数组长度-1
    for (let i = 0; i < originValues.length - 1; i++) {
        // 两两比较，该迭代的最大数，移动到右侧相应位置
        for (let j = 0; j < originValues.length - 1 - i; j++) {
            // 如果前一个数，大于后一个数，交换
            if (originValues[j] > originValues[j + 1]) {
                const tmp = originValues[j];
                originValues[j] = originValues[j + 1];
                originValues[j + 1] = tmp;
            }
        }
    }

    return originValues;
};

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

  • Самая внешняя петля(length-1)
    Это смотрит на многие реализации как на внешние циклыlengthНа самом деле последний раз избыточен, потому что пока отсортированы первые n-1, первое число должно быть наименьшим числом.
  • Внутренний цикл может игнорировать уже отсортированные элементы
    После каждых n раундов необходимо упорядочить n самых правых элементов. При сортировке подкачки эти элементы можно игнорировать. так Курсор завершения для внутреннего циклаlength-1-i.

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

улучшенное барботирование

Код выглядит следующим образом, см.bubble_sort_2.js.

const bubbleSort = (array) => {
    // 不修改原数组
    const originValues = array.slice(); 

    let swapped = true;
    do {
        // 标记该次迭代是否交换顺序，如果没有，代表列表已经有序
        swapped = false;
        for (let i = 0; i < originValues.length - 1; i++) {
            // 如果前一元素大于后一元素，交换顺序
            if (originValues[i] > originValues[i + 1]) {
                const tmp = originValues[i];
                originValues[i] = originValues[i + 1];
                originValues[i + 1] = tmp;
                // 如果有交换，标记继续下一轮
                swapped = true;
            }
        }
    } while (swapped);

    return originValues;
};

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

Выделите, а затем измените

Код выглядит следующим образом, см.bubble_sort_3.js.

const bubbleSort = (array) => {
    // 不修改原数组
    const originValues = array.slice(); 

    let swapped = true;
    let hasOrderedCnt = 0; // 已排序个数
    do {
        // 标记该次迭代是否交换顺序，如果没有，代表列表已经有序
        swapped = false;
        for (let i = 0; i < originValues.length - 1 - hasOrderedCnt; i++) {
            // 如果前一元素大于后一元素，交换顺序
            if (originValues[i] > originValues[i + 1]) {
                const tmp = originValues[i];
                originValues[i] = originValues[i + 1];
                originValues[i + 1] = tmp;
                swapped = true;
            }
        }
        // 每一轮之后，都有一个元素排好顺序
        hasOrderedCnt++;
    } while (swapped);

    return originValues;
};

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

Анализ алгоритмов

  • временная сложность
    После нескольких раундов модификации, когда массив находится в положительном порядке, оптимальная сложность может достигать O(n), а когда массив находится в обратном порядке, наихудшая сложность равна O(n).2).

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

Суммировать

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

Ссылаться на

[1] анимация
[2] учебные пособия
[3] The Bubble sort algorithm
[4] Sorting Algorithms

Категории