Сортировка пузырьком на Java: принцип, примеры и реализация
Сортировка пузырьком (bubble sort) является одним из простейших алгоритмов сортировки. Он прост в реализации, но имеет квадратичную сложность, что делает его неэффективным для больших массивов.
Принцип сортировки пузырьком заключается в сравнении пар соседних элементов массива и обмене их местами, если они находятся в неправильном порядке. При каждом проходе по массиву, большие элементы «всплывают» к верхней части массива, а меньшие остаются на месте.
Пример реализации сортировки пузырьком на языке Java:
public class BubbleSort {
public static void bubbleSort(int[] arr) {
boolean isSorted = false;
int lastUnsorted = arr.length - 1;
while (!isSorted) {
isSorted = true;
for (int i = 0; i < lastUnsorted; i++) {
if (arr[i] > arr[i + 1]) {
swap(arr, i, i + 1);
isSorted = false;
}
}
lastUnsorted--;
}
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
int[] arr = { 5, 2, 8, 3, 1, 6 };
bubbleSort(arr);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}
В этом коде мы использовали два вспомогательных метода swap и main. swap используется для обмена местами двух элементов массива, а main используется для демонстрации работы метода bubbleSort.
Метод bubbleSort принимает на вход массив arr и сортирует его с помощью алгоритма сортировки пузырьком. Изначально мы устанавливаем флаг isSorted в false и переменную lastUnsorted равной длине массива минус единица (поскольку последний элемент уже отсортирован). Затем мы запускаем цикл while, который будет продолжаться, пока isSorted не станет равным true.
Внутри цикла мы перебираем элементы массива с помощью цикла for и сравниваем каждый элемент с его соседями. Если два соседних элемента находятся в неправильном порядке, мы вызываем метод swap и меняем их местами. Если в результате прохода всех элементов мы не произвели ни одной замены, значит массив уже отсортирован, и мы можем выйти из цикла.
На выходе из метода мы получаем отсортированный массив, который мы можем перебрать с помощью цикла for и вывести на экран.