Основные сортировки

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

List<Integer> list = new ArrayList<>(List.of(5, 2, 8, 1));
Collections.sort(list);          // [1, 2, 5, 8]

int[] arr = {5, 2, 8, 1};
Arrays.sort(arr);                  // [1, 2, 5, 8]

Сортировка пузырьком (bubble sort) — самая простая для понимания идея: сравниваем соседние элементы и меняем местами, если они не по порядку, и так несколько проходов подряд:

void bubbleSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }
        }
    }
}

Копнуть глубже

Почему bubbleSort — это O(n²). Два вложенных цикла, каждый примерно по n элементов — отсюда n × n. На маленьких данных незаметно, на больших — катастрофически медленно.

Эффективные сортировки работают за O(n log n) — это теоретический предел для сортировки сравнением. Идея, например, у сортировки слиянием (merge sort): разбить массив пополам, отсортировать каждую половину рекурсивно, потом слить две отсортированные половины за один проход:

Сортировка	Сложность	Идея
Bubble sort	O(n²)	сравнение соседей, много проходов
Merge sort	O(n log n)	разделяй и властвуй, слияние
Quick sort	O(n log n) в среднем	разделяй и властвуй, опорный элемент

Collections.sort()/Arrays.sort() в Java под капотом используют оптимизированные версии merge sort (для объектов) и quicksort-подобные алгоритмы (для примитивов) — писать сортировку руками в реальном коде не нужно, важно понимать, что внутри.

🎤 Закрыл тему, если можешь объяснить:

• как работает сортировка пузырьком и почему она O(n²);
• идею сортировки слиянием и почему O(n log n) лучше (если дошёл до 2-го слоя).