Сортировка пузырьком в Java - Вопросы

За каждый проход наименьший (или наибольший — в зависимости от направления) элемент постепенно «всплывает» к краю массива, как пузырёк воздуха поднимается в воде. Отсюда названия «пузырьковая сортировка», «метод пузырька» и английское bubble sort.

В среднем и худшем случае — O(n²), где n это число элементов. Лучший случай — O(n), но только в оптимизированной версии с флагом, когда массив уже отсортирован. По памяти алгоритм работает за O(1), так как сортирует на месте.

Добавьте логический флаг swapped: если за очередной проход не было ни одного обмена, массив уже отсортирован и цикл можно прервать через break. Это снижает сложность лучшего случая до O(n) и полезно, когда данные почти упорядочены.

Оба алгоритма имеют сложность O(n²), но пузырьковая сортировка сравнивает и меняет местами соседние элементы, а сортировка выбором за каждый проход находит минимум и делает лишь один обмен. Из-за этого метод пузырька выполняет больше перестановок, зато он устойчивый, а классическая сортировка выбором — нет.

Да, сортировка пузырьком устойчивая (стабильная): равные элементы сохраняют исходный взаимный порядок, потому что обмен выполняется только для строго большего элемента (условие array[j - 1] > array[j], а не >=). Эта деталь часто всплывает на собеседованиях.