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

Если вы когда-нибудь задумывались над тем, что заставляет работать алгоритм пузырьковой сортировки и как он работает, то вы обратились по адресу!

Давайте углубимся!

Что такое алгоритм пузырьковой сортировки?

Алгоритм пузырьковой сортировки — это простой алгоритм сортировки, который многократно перебирает список элементов, сравнивает соседние пары и меняет их местами, если они расположены в неправильном порядке. Этот процесс повторяется до тех пор, пока весь список не будет отсортирован.

Как это работает?

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

Чтобы его алгоритм можно было легко усвоить, мы собираемся реализовать его, решив вызов LeetCode ниже.

Задача состоит в том, чтобы отсортировать массив с n объектами, окрашенными в красный, белый или синий цвет, отсортировать их на месте, чтобы объекты одного и того же цвета были рядом, с цветами в порядке красного, белый и синий.

Используйте целые числа 0, 1 и 2 в качестве художественной палитры для представления красного, белого и синего цветов. Помните, задача состоит в том, чтобы справиться с этой задачей без помощи библиотечной функции сортировки.

Пример 1:

Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

Пример 2:

Input: nums = [2,0,1]
Output: [0,1,2]

Внимательно посмотрите на следующую реализацию алгоритма пузырьковой сортировки:

Давайте проанализируем построчную реализацию алгоритма пузырьковой сортировки, специально предназначенного для сортировки массива цветов, представленных числами.

  1. Функция sortColors принимает массив nums в качестве параметра и стремится изменить массив на месте.
  2. Первый цикл for инициализирует переменную i значением 0 и повторяется до тех пор, пока i не станет меньше длины массива nums.
  3. Внутри первого цикла используется вложенный цикл for, инициализирующий переменную j значением 0 и повторяющийся до тех пор, пока j не станет меньше длины массива nums.
  4. Во вложенном цикле оператор if проверяет, меньше ли элемент с индексом i, чем элемент с индексом j в массиве nums. Если это правда, это означает, что элементы расположены в неправильном порядке.
  5. Если условие выполнено, используется назначение деструктуризации массива для замены элементов с индексами i и j в массиве nums. Этот обмен достигается путем создания временного массива и присвоения значений в нужном порядке.
  6. После завершения вложенного цикла внешний цикл переходит к следующей итерации, и процесс повторяется до тех пор, пока не будет пройден весь массив.
  7. Наконец, функция возвращает измененный массив nums, который теперь содержит отсортированные цвета.

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

Тогда как насчет временной и пространственной сложности?

  • Временная сложность.
    С точки зрения временной сложности алгоритм пузырьковой сортировки имеет временную сложность в наихудшем случае O(n²), где n – количество элементов в массиве. Это происходит, когда массив находится в обратном порядке, что требует максимального количества сравнений и перестановок. Наилучшая временная сложность составляет O(n), когда массив уже отсортирован, так как свопы не нужны. В среднем пузырьковая сортировка имеет временную сложность O(n²).
  • Объемная сложность:
    Объемная сложность кода составляет O(1), поскольку он использует постоянное количество дополнительного пространства, которое не зависит от размера входных данных. Сортировка выполняется на месте, непосредственно изменяя исходный массив «nums». Никаких дополнительных структур данных не используется.

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

Спасибо, что прочитали эту статью!!!!!!