Bubble Алгоритм сортировки в Java: Программа и пример сортировки массива
Джеймс Хартман
⚡ Умное резюме
Bubble Алгоритм сортировки в Java Многократно сравнивает соседние элементы массива и меняет их местами до тех пор, пока последовательность не будет упорядочена. В этой статье объясняется механизм работы, приводится псевдокод и полный текст. Java Реализация, оптимизированный вариант, анализ сложности и практическое сравнение с другими методами сортировки.
Что такое Bubblе Сортировать?
Bubble-сортировка — это простой алгоритм сортировки, основанный на сравнении, который сравнивает первый элемент массива со следующим. Если текущий элемент массива численно больше следующего, элементы меняются местами. Аналогичным образом алгоритм проходит по всем элементам массива.
Алгоритм получил свое название благодаря тому, как наибольшее значение в несортированной области неуклонно поднимается к своей конечной позиции, подобно пузырьку, поднимающемуся на поверхность воды. После первого полного прохода наибольший элемент занимает последний индекс. После второго прохода второй по величине элемент фиксируется на месте, и процесс повторяется до тех пор, пока массив не будет полностью упорядочен.
В этой статье мы создадим Java программа по реализации Bubble. Сортировка. Проверьте вывод кода, который поможет вам понять логику программы, а затем просмотрите оптимизированную версию и последующий анализ сложности.
Как BubblРаботает ли алгоритм сортировки?
BubblСортировка e работает путем многократного прохода по массиву. Каждый проход идет от первого индекса до конца неотсортированной области, сравнивая соседние значения и меняя их местами.ping их всякий раз, когда они появляются в неправильном порядке. Поскольку наибольшее оставшееся значение всегда перемещается в крайнюю правую часть несортированной области, эта область сужается ровно на одну позицию после каждого прохода.
Весь процесс можно разбить на четыре повторяющихся этапа:
- Для сравнения: Сравните элемент с индексом j-1 с элементом с индексом j.
- Обмен: Если левый элемент больше правого, поменяйте местами значения, используя временную переменную.
- Advance: Переместитесь на одну позицию вправо и повторяйте действия до тех пор, пока не достигнете конца несортированной области.
- Повторение: Начните новый проход по области, которая на один элемент короче, и остановитесь после n-1 проходов или когда проход не выполнит ни одной перестановки.
Таблица ниже tracЭто пример массива {860, 8, 200, 9}, используемый в программе, которая будет приведена далее на этой странице. Он точно показывает, какое значение занимает свою конечную позицию в конце каждого прохода.
| Проходить | Массив в начале прохода | Проведены сравнения | Массив в конце прохода | Элемент заблокирован |
|---|---|---|---|---|
| 1 | 860, 8, 200, 9 | 3 | 8, 200, 9, 860 | 860 |
| 2 | 8, 200, 9, 860 | 2 | 8, 9, 200, 860 | 200 |
| 3 | 8, 9, 200, 860 | 1 | 8, 9, 200, 860 | 9 |
| 4 | 8, 9, 200, 860 | 0 | 8, 9, 200, 860 | 8 |
Обратите внимание, что на третьем проходе выполняется сравнение, но не обмен. Оптимизированная реализация обнаруживает это условие и немедленно останавливается, что является самым ценным улучшением, которое можно внести в этот алгоритм.
BubblПсевдокод алгоритма сортировки
Перед написанием Java Синтаксис помогает выразить логику в нейтральном для языка псевдокоде. Приведенная ниже версия включает флаг раннего выхода, поэтому она охватывает как классическое, так и оптимизированное поведение.
procedure bubbleSort(array A, integer n) for i from 0 to n - 2 do swapped := false for j from 1 to n - i - 1 do // compare the adjacent pair if A[j - 1] > A[j] then swap A[j - 1] and A[j] swapped := true end if end for // no swap in a full pass means the array is sorted if swapped = false then break end if end for end procedure
Внешний цикл управляет количеством проходов, а внутренний цикл — сравнениями внутри одного прохода. Верхняя граница внутреннего цикла равна n – i – 1, поскольку последние i позиций уже содержат свои окончательные значения.
Java Программа реализации Bubblэлектронная сортировка
Следующая программа сортирует массив целых чисел в порядке возрастания. Дополнительные операторы print намеренно оставлены внутри циклов, поскольку чтение пошагового вывода данных может быть затруднено. trace — это самый быстрый способ для новичка понять, как накапливаются свопы.
package com.guru99; public class BubbleSort { public static void main(String[] args) { int arr[] = {860, 8, 200, 9}; System.out.println("---Array BEFORE Bubble Sort---"); printArray(arr); bubbleSort(arr); //sorting array elements using bubble sort System.out.println("---Array AFTER Bubble Sort---"); printArray(arr); } static void bubbleSort(int[] array) { int n = array.length; int temp = 0; for(int i = 0; i < n; i++) // Looping through the array length { System.out.println("Sort Pass Number " + (i + 1)); for(int j = 1; j < (n - i); j++) { System.out.println("Comparing " + array[j - 1] + " and " + array[j]); if(array[j - 1] > array[j]) { //swap elements temp = array[j - 1]; array[j - 1] = array[j]; array[j] = temp; System.out.println(array[j] + " is greater than " + array[j - 1]); System.out.println("Swapping Elements: New Array After Swap"); printArray(array); } } } } static void printArray(int[] array){ for(int i = 0; i < array.length; i++) { System.out.print(array[i] + " "); } System.out.println(); } }
Выход:
---Array BEFORE Bubble Sort--- 860 8 200 9 Sort Pass Number 1 Comparing 860 and 8 860 is greater than 8 Swapping Elements: New Array After Swap 8 860 200 9 Comparing 860 and 200 860 is greater than 200 Swapping Elements: New Array After Swap 8 200 860 9 Comparing 860 and 9 860 is greater than 9 Swapping Elements: New Array After Swap 8 200 9 860 Sort Pass Number 2 Comparing 8 and 200 Comparing 200 and 9 200 is greater than 9 Swapping Elements: New Array After Swap 8 9 200 860 Sort Pass Number 3 Comparing 8 and 9 Sort Pass Number 4 ---Array AFTER Bubble Sort--- 8 9 200 860
Code объяснение: bubbleSort Метод получает массив по ссылке, поэтому вызывающая сторона видит отсортированный результат без возвращаемого значения. Переменная температура Во время обмена тремя строками хранится одно значение, поэтому алгоритму требуется всего O(1) дополнительной памяти. Выражение н – и В условии внутреннего цикла гарантируется, что уже отсортированные позиции в хвосте никогда не будут повторно посещены.
Оптимизированный BubblПрограмма e Sort в Java
Приведенная выше программа всегда выполняет n-1 проходов, даже если массив отсортирован на ранней стадии. Добавление одного логического флага устраняет эту неэффективность. Если полный проход завершается без единого обмена, гарантируется, что массив отсортирован, и внешний цикл может немедленно остановиться.
package com.guru99; public class OptimizedBubbleSort { public static void main(String[] args) { int arr[] = {5, 12, 33, 47, 58}; bubbleSort(arr); System.out.println(java.util.Arrays.toString(arr)); } static void bubbleSort(int[] array) { int n = array.length; int passes = 0; for (int i = 0; i < n - 1; i++) { boolean swapped = false; for (int j = 1; j < n - i; j++) { if (array[j - 1] > array[j]) { int temp = array[j - 1]; array[j - 1] = array[j]; array[j] = temp; swapped = true; } } passes++; // Early exit: the array is already sorted if (!swapped) { break; } } System.out.println("Passes executed: " + passes); } }
Выход:
Passes executed: 1 [5, 12, 33, 47, 58]
Входной массив уже был отсортирован, поэтому оптимизированная версия завершилась за один проход вместо четырех. На почти отсортированных данных это изменение превращает квадратичную нагрузку в почти линейную, что является основной причиной. BubblСортировка e по-прежнему время от времени встречается в реальном коде.
Временная и пространственная сложность Bubblэлектронная сортировка
Сложность описывает, как время выполнения возрастает с увеличением размера входных данных. BubblВ неоптимизированной версии количество сравнений фиксировано на уровне n(n-1)/2, что прочно помещает её в квадратичный класс.
| Сценарий | Входное условие | Сложность времени | Космическая сложность |
|---|---|---|---|
| лучший случай | Массив уже отсортирован, оптимизированная версия. | О (п) | O (1) |
| Средний случай | Элементы в случайном порядке | O (n²) | O (1) |
| Худший случай | Массив отсортирован в обратном порядке. | O (n²) | O (1) |
Поскольку все обмены происходят внутри исходного массива и используется только одна временная переменная, Bubble-сортировка — это алгоритм сортировки на месте с вспомогательным пространством O(1). Это также стабильная сортировка, то есть две записи, содержащие один и тот же ключ, сохраняют свой первоначальный относительный порядок после сортировки.
Преимущества и недостатки Bubblэлектронная сортировка
Понимание обеих сторон поможет вам решить, когда алгоритм является приемлемым вариантом, а когда его следует заменить.
Преимущества
- Простота: Логика умещается примерно в десять строк, что позволяет легко и корректно изложить её в условиях собеседования.
- Работа на месте: Вспомогательный массив не выделяется, поэтому объем используемой памяти не увеличивается с размером входных данных.
- Стабильность: Ключи, имеющие одинаковый порядок, сохраняют свой первоначальный вид, что важно при сортировке записей по дополнительному полю.
- Раннее обнаружение выхода: Флаг swapped указывает на то, что массив уже отсортирован за один проход.
Недостатки
- Квадратичный рост: Для сортировки 10 000 элементов в худшем случае потребуется почти 50 миллионов сравнений.
- Excessive пишет: Этот алгоритм выполняет гораздо больше операций обмена, чем сортировка выбором, которая требует больших затрат памяти и характеризуется медленными операциями записи.
- Низкая масштабируемость: В производственных задачах почти всегда предпочтение отдается быстрой сортировке (Quicksort), сортировке слиянием (Merge Sort) или встроенному методу Arrays.sort.
💡 Совет: В производстве Java код, предпочтительно Arrays.sort () для примитивов и Collections.sort() для списков. Оба алгоритма, Dual-Pivot Quicksort и TimSort соответственно, используют высокоэффективные алгоритмы, превосходящие написанный вручную. Bubble. Сортировка по порядкам величины.
Bubble-сортировка против других методов сортировки Algorithms
В таблице ниже сравниваются Bubble. Используйте методы сортировки, которые позже освоят новички, чтобы точно определить, в чем заключается преимущество каждого из них.
| Алгоритм | лучший случай | Средний случай | Худший случай | Space | Стабильный |
|---|---|---|---|---|---|
| Bubblэлектронная сортировка | О (п) | O (n²) | O (n²) | O (1) | Да |
| Выбор сортировки | O (n²) | O (n²) | O (n²) | O (1) | Нет |
| Сортировка вставки | О (п) | O (n²) | O (n²) | O (1) | Да |
| Быстрая сортировка | O (п войти п) | O (п войти п) | O (n²) | O (журнал n) | Нет |
| Сортировка кучи | O (п войти п) | O (п войти п) | O (п войти п) | O (1) | Нет |
BubblСортировка e и сортировка вставками имеют одинаковый линейный наилучший случай, но сортировка вставками выполняет меньше перестановок на частично отсортированных данных. Сортировка выбором всегда выполняет ровно n-1 перестановок, что делает её наиболее эффективной.tracЭтот метод предпочтительнее, когда операции записи затратны, хотя и жертвует стабильностью. Для любого массива, превышающего несколько сотен элементов, правильным выбором будет быстрая сортировка или сортировка кучей.
Как только вы освоите используемые здесь схемы обхода массивов, та же структура цикла будет встречаться во многих классических упражнениях, таких как... Последовательность Фибоначчи в Java и Java программа палиндромов. Revмероприятие Java массивы и более широких Java учебник это укрепит фундаментальные основы, на которых основан этот алгоритм.
