Алгоритмы сортировки в Java: подробное руководство

Что это такое и зачем? (аналогия из реальной жизни)

Представьте, что вы — библиотекарь. Каждый день в библиотеку привозят десятки новых книг. Их нужно расставить по полкам в алфавитном порядке. Если вы будете просто класть книги стопкой, то читатель никогда не найдёт нужную. Но если вы потратите время и разложите всё по порядку — поиск станет делом нескольких секунд.

Сортировка в программировании — это ровно то же самое. Это процесс упорядочивания данных по определённому правилу (чаще всего — по возрастанию или убыванию). Без сортировки невозможно представить ни одну серьёзную программу: поиск, базы данных, рекомендации в интернете, расписание поездов — везде данные должны быть упорядочены.

Запомните главное правило: сортировка превращает хаос в порядок. А порядок — это скорость и эффективность работы программы.

Представьте, что у вас есть массив чисел: [5, 3, 8, 1, 9]. После сортировки по возрастанию он превратится в [1, 3, 5, 8, 9]. Теперь найти число 8 можно за один взгляд, а не перебирать все элементы.

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

Теория: как это работает изнутри

Чтобы понять сортировку, нужно разобраться в трёх ключевых понятиях: сравнение, обмен и сложность.

Сравнение и обмен

Любой алгоритм сортировки делает две вещи:

• Сравнивает два элемента (например, 5 > 3?)
• Меняет их местами, если порядок нарушен

В Java сравнение делается операторами <, >, == или через метод compareTo() для объектов. Обмен — через временную переменную:

int temp = a;  // сохраняем первое число
a = b;         // на место первого ставим второе
b = temp;      // на место второго ставим сохранённое первое

Сложность алгоритмов (Big O)

Это способ измерить, насколько быстро работает алгоритм. Представьте, что у вас 1000 чисел. Один алгоритм сделает 500 000 операций, а другой — всего 10 000. Разница колоссальна!

Обозначение	Название	Пример для 1000 элементов
O(n²)	Квадратичная	~1 000 000 операций (пузырьковая)
O(n log n)	Логарифмическая	~10 000 операций (быстрая)
O(n)	Линейная	~1000 операций (идеал, но редко)

Важно: O(n²) — это медленно. O(n log n) — быстро. Для маленьких массивов (до 100 элементов) разница незаметна, но для больших данных выбор алгоритма критичен.

Стабильность сортировки

Если два элемента равны, сохранят ли они свой исходный порядок? Если да — сортировка стабильная. Это важно, когда сортируем сложные объекты (например, сначала по имени, потом по возрасту).

Синтаксис в Java: все формы и варианты

Java предоставляет несколько способов сортировки. От самых простых (для новичков) до профессиональных (для продакшена).

1. Arrays.sort() — для массивов

Самый простой способ. Использует быструю сортировку (Dual-Pivot Quicksort) для примитивов и TimSort для объектов.

import java.util.Arrays;

int[] numbers = {5, 3, 8, 1, 9};
Arrays.sort(numbers);  // теперь numbers = [1, 3, 5, 8, 9]

2. Collections.sort() — для списков

Для ArrayList, LinkedList и других коллекций:

import java.util.ArrayList;
import java.util.Collections;

ArrayList<String> names = new ArrayList<>();
names.add("Иван");
names.add("Анна");
names.add("Пётр");
Collections.sort(names);  // [Анна, Иван, Пётр]

3. Сортировка в обратном порядке

Используем Comparator.reverseOrder():

Arrays.sort(numbers);  // по возрастанию
// для обратного порядка:
Integer[] nums = {5, 3, 8, 1, 9};
Arrays.sort(nums, Collections.reverseOrder());  // [9, 8, 5, 3, 1]

Внимание: reverseOrder() работает только с объектами (Integer, String), не с примитивами (int).

4. Сортировка объектов по полям

Допустим, у нас есть класс Student с полями name и grade. Хотим отсортировать студентов по оценкам:

import java.util.*;

class Student {
    String name;
    int grade;
    
    Student(String name, int grade) {
        this.name = name;
        this.grade = grade;
    }
}

// Сортировка через Comparator
Collections.sort(students, new Comparator<Student>() {
    @Override
    public int compare(Student s1, Student s2) {
        return Integer.compare(s1.grade, s2.grade);
    }
});

// Или через лямбду (современный способ):
students.sort((s1, s2) -> Integer.compare(s1.grade, s2.grade));

5. Сортировка через Stream API

Современный функциональный стиль (Java 8+):

List<Integer> sortedList = numbers.stream()
    .sorted()
    .collect(Collectors.toList());

// Сортировка объектов по полю:
List<Student> sortedStudents = students.stream()
    .sorted(Comparator.comparingInt(s -> s.grade))
    .collect(Collectors.toList());

Примеры кода — от простого к сложному

Пример 1: Пузырьковая сортировка (Bubble Sort)

Самый простой для понимания, но медленный. Соседние элементы сравниваются и меняются местами, если порядок нарушен. "Тяжёлые" элементы всплывают в конец, как пузырьки в воде.

public class BubbleSortExample {
    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        
        System.out.println("Исходный массив:");
        printArray(arr);
        
        bubbleSort(arr);
        
        System.out.println("Отсортированный массив:");
        printArray(arr);
    }
    
    // Метод пузырьковой сортировки
    static void bubbleSort(int[] arr) {
        int n = arr.length;
        
        // Внешний цикл: каждый проход ставит один элемент на место
        for (int i = 0; i < n - 1; i++) {
            
            // Внутренний цикл: сравниваем соседние элементы
            for (int j = 0; j < n - i - 1; j++) {
                
                // Если текущий элемент больше следующего — меняем
                if (arr[j] > arr[j + 1]) {
                    // Обмен через временную переменную
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
    
    // Вспомогательный метод для вывода массива
    static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

Объяснение: Внешний цикл выполняется n-1 раз. Внутренний — каждый раз на один элемент меньше, потому что самый большой элемент уже "всплыл" в конец. Сложность: O(n²).

Пример 2: Сортировка выбором (Selection Sort)

На каждом шаге находим минимальный элемент и ставим его в начало. Интуитивно понятно: "найди самый маленький и поставь первым".

public class SelectionSortExample {
    public static void main(String[] args) {
        int[] arr = {29, 10, 14, 37, 13};
        
        System.out.println("Исходный массив:");
        printArray(arr);
        
        selectionSort(arr);
        
        System.out.println("Отсортированный массив:");
        printArray(arr);
    }
    
    static void selectionSort(int[] arr) {
        int n = arr.length;
        
        // Проходим по всем элементам, кроме последнего
        for (int i = 0; i < n - 1; i++) {
            
            // Считаем, что текущий элемент — минимальный
            int minIndex = i;
            
            // Ищем реальный минимальный элемент в оставшейся части
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;  // нашли новый минимум
                }
            }
            
            // Меняем местами текущий элемент с найденным минимумом
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }
    
    static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

Объяснение: На каждом шаге мы делаем один обмен. Это лучше пузырьковой сортировки, но сложность всё ещё O(n²).

Пример 3: Сортировка вставками (Insertion Sort)

Представьте, что вы собираете колоду карт. Берёте новую карту и вставляете её в нужное место среди уже отсортированных. Отлично работает для почти отсортированных данных.

public class InsertionSortExample {
    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6};
        
        System.out.println("Исходный массив:");
        printArray(arr);
        
        insertionSort(arr);
        
        System.out.println("Отсортированный массив:");
        printArray(arr);
    }
    
    static void insertionSort(int[] arr) {
        int n = arr.length;
        
        // Начинаем со второго элемента (первый считаем отсортированным)
        for (int i = 1; i < n; i++) {
            int key = arr[i];  // элемент, который нужно вставить
            int j = i - 1;     // индекс предыдущего элемента
            
            // Сдвигаем элементы вправо, пока не найдём место для key
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];  // сдвиг
                j--;
            }
            
            // Вставляем key на найденное место
            arr[j + 1] = key;
        }
    }
    
    static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

Объяснение: Для каждого элемента мы "сдвигаем" большие элементы вправо, освобождая место. Лучший случай (уже отсортированный массив) — O(n), худший — O(n²).

Пример 4: Быстрая сортировка (Quick Sort)

Самый популярный алгоритм. Работает по принципу "разделяй и властвуй": выбираем опорный элемент, делим массив на две части (меньше опорного и больше), рекурсивно сортируем каждую часть.

public class QuickSortExample {
    public static void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5};
        
        System.out.println("Исходный массив:");
        printArray(arr);
        
        quickSort(arr, 0, arr.length - 1);
        
        System.out.println("Отсортированный массив:");
        printArray(arr);
    }
    
    // Главный метод быстрой сортировки
    static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // Находим индекс опорного элемента после разделения
            int pi = partition(arr, low, high);
            
            // Рекурсивно сортируем левую и правую части
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }
    
    // Метод разделения массива на две части
    static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];  // выбираем последний элемент как опорный
        int i = low - 1;        // индекс меньшего элемента
        
        // Проходим по всем элементам от low до high-1
        for (int j = low; j < high; j++) {
            // Если текущий элемент меньше или равен опорному
            if (arr[j] <= pivot) {
                i++;
                
                // Меняем местами arr[i] и arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        
        // Ставим опорный элемент на правильное место
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        
        return i + 1;  // возвращаем индекс опорного элемента
    }
    
    static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

Объяснение: Рекурсия делит массив пополам. В среднем случае сложность O(n log n), но в худшем (если массив уже отсортирован) — O(n²).

Пример 5: Сортировка слиянием (Merge Sort)

Тоже "разделяй и властвуй", но гарантированно быстрая. Делим массив пополам, сортируем каждую половину, затем сливаем две отсортированные половины в одну.

public class MergeSortExample {
    public static void main(String[] args) {
        int[] arr = {38, 27, 43, 3, 9, 82, 10};
        
        System.out.println("Исходный массив:");
        printArray(arr);
        
        mergeSort(arr, 0, arr.length - 1);
        
        System.out.println("Отсортированный массив:");
        printArray(arr);
    }
    
    // Рекурсивный метод сортировки слиянием
    static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int middle = left + (right - left) / 2;  // находим середину
            
            // Сортируем левую и правую половины
            mergeSort(arr, left, middle);
            mergeSort(arr, middle + 1, right);
            
            // Сливаем отсортированные половины
            merge(arr, left, middle, right);
        }
    }
    
    // Метод слияния двух отсортированных подмассивов
    static void merge(int[] arr, int left, int middle, int right) {
        // Размеры временных массивов
        int n1 = middle - left + 1;
        int n2 = right - middle;
        
        // Создаём временные массивы
        int[] leftArr = new int[n1];
        int[] rightArr = new int[n2];
        
        // Копируем данные во временные массивы
        for (int i = 0; i < n1; i++) {
            leftArr[i] = arr[left + i];
        }
        for (int j = 0; j < n2; j++) {
            rightArr[j] = arr[middle + 1 + j];
        }
        
        // Индексы для прохода по массивам
        int i = 0, j = 0;
        int k = left;  // индекс в основном массиве
        
        // Сливаем два массива в один, сравнивая элементы
        while (i < n1 && j < n2) {
            if (leftArr[i] <= rightArr[j]) {
                arr[k] = leftArr[i];
                i++;
            } else {
                arr[k] = rightArr[j];
                j++;
            }
            k++;
        }
        
        // Копируем оставшиеся элементы из левого массива
        while (i < n1) {
            arr[k] = leftArr[i];
            i++;
            k++;
        }
        
        // Копируем оставшиеся элементы из правого массива
        while (j < n2) {
            arr[k] = rightArr[j];
            j++;
            k++;
        }
    }
    
    static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

Объяснение: Всегда O(n log n), но требует дополнительной памяти O(n). Стабильная сортировка.

Пример 6: Сортировка через Arrays.sort() с компаратором

Профессиональный способ сортировки объектов по нескольким полям:

import java.util.*;

public class AdvancedSortExample {
    public static void main(String[] args) {
        // Создаём список студентов
        ArrayList<Student> students = new ArrayList<>();
        students.add(new Student("Иван", 85, 18));
        students.add(new Student("Анна", 92, 17));
        students.add(new Student("Пётр", 85, 19));
        students.add(new Student("Мария", 78, 18));
        
        System.out.println("До сортировки:");
        for (Student s : students) {
            System.out.println(s);
        }
        
        // Сортировка по оценке (по убыванию), затем по имени (по возрастанию)
        students.sort(new Comparator<Student>() {
            @Override
            public int compare(Student s1, Student s2) {
                // Сначала сравниваем по оценке
                int gradeCompare = Integer.compare(s2.grade, s1.grade);
                if (gradeCompare != 0) {
                    return gradeCompare;  // если оценки разные — возвращаем результат
                }
                // Если оценки равны — сравниваем по имени
                return s1.name.compareTo(s2.name);
            }
        });
        
        System.out.println("
После сортировки (по оценке убыв., затем по имени):");
        for (Student s : students) {
            System.out.println(s);
        }
    }
}

class Student {
    String name;
    int grade;
    int age;
    
    Student(String name, int grade, int age) {
        this.name = name;
        this.grade = grade;
        this.age = age;
    }
    
    @Override
    public String toString() {
        return name + " (оценка: " + grade + ", возраст: " + age + ")";
    }
}

Объяснение: Компаратор позволяет задать любую логику сравнения. Сначала сравниваем по оценке (обратный порядок), если оценки равны — по имени (прямой порядок).

Пример 7: Сортировка строк с учётом локали

Русские буквы сортируются не так, как английские. Используем Collator для правильной сортировки:

import java.text.Collator;
import java.util.*;

public class LocaleSortExample {
    public static void main(String[] args) {
        String[] words = {"ёлка", "елка", "яблоко", "апельсин", "Юлия", "юла"};
        
        System.out.println("Исходный массив:");
        System.out.println(Arrays.toString(words));
        
        // Обычная сортировка (неправильная для русского)
        Arrays.sort(words);
        System.out.println("Обычная сортировка:");
        System.out.println(Arrays.toString(words));
        
        // Правильная сортировка с учётом русского языка
        Collator collator = Collator.getInstance(new Locale("ru"));
        Arrays.sort(words, collator);
        
        System.out.println("Сортировка с учётом русской локали:");
        System.out.println(Arrays.toString(words));
    }
}

Объяснение: Collator учитывает правила русского языка: буква "ё" идёт после "е", заглавные и строчные буквы обрабатываются корректно.

Сравнение с Python: чем похоже и чем отличается

Характеристика	Java	Python
Встроенная сортировка	Arrays.sort(), Collections.sort()	sorted(), list.sort()
Сортировка в обратном порядке	Collections.reverseOrder()	reverse=True
Сортировка объектов	Через Comparator или Comparable	Через key или __lt__
Стабильность	Стабильная для объектов, нестабильная для примитивов	Всегда стабильная
Производительность	Быстрее (компилируемый язык)	Медленнее (интерпретируемый язык)
Сложность написания	Больше кода, строже типизация	Меньше кода, динамическая типизация

Главное отличие: В Python сортировка — это одна строка кода. В Java нужно больше писать, но зато контроль над процессом полный. Python использует TimSort (гибрид сортировки слиянием и вставками), Java — Dual-Pivot Quicksort для примитивов и TimSort для объектов.

Совет: Если вы знаете Python, то в Java вам будет непривычно многословно. Но это плата за скорость и надёжность. Java-программы работают быстрее и предсказуемее.

Типичные ошибки и подводные камни

Ошибка 1: Забыли про границы массива

Самая частая ошибка новичков — выход за пределы массива. В цикле for (int j = 0; j < n - i - 1; j++) легко ошибиться с n - i - 1.

// Ошибка: выход за границы
for (int j = 0; j < n - i; j++) {  // при j = n-i-1 будет обращение к arr[n-i]
    if (arr[j] > arr[j + 1]) {     // arr[j+1] = arr[n-i] — выход за границу!
        // ...
    }
}

Ошибка 2: Сортировка примитивов в обратном порядке

Collections.reverseOrder() не работает с int[]. Нужно использовать Integer[].

int[] numbers = {5, 3, 8, 1, 9};
// Arrays.sort(numbers, Collections.reverseOrder());  // ОШИБКА!
// Правильно:
Integer[] nums = {5, 3, 8, 1, 9};
Arrays.sort(nums, Collections.reverseOrder());

Ошибка 3: Неправильное сравнение объектов

При сортировке объектов нужно правильно реализовать compareTo() или compare(). Частая ошибка — возвращать только 0 или 1, а не -1, 0, 1.

// Неправильно:
public int compare(Student s1, Student s2) {
    if (s1.grade > s2.grade) return 1;
    else return 0;  // забыли про случай s1.grade < s2.grade
}

// Правильно:
public int compare(Student s1, Student s2) {
    return Integer.compare(s1.grade, s2.grade);
}

Ошибка 4: Изменение массива во время сортировки

Если вы используете Stream API, исходный массив не меняется. Новички часто забывают присвоить результат.

int[] numbers = {5, 3, 8, 1, 9};
Arrays.stream(numbers).sorted().toArray();  // numbers не изменился!
// Правильно:
int[] sorted = Arrays.stream(numbers).sorted().toArray();

Ошибка 5: Сортировка с null значениями

Если в массиве есть null, сортировка упадёт с NullPointerException.

String[] names = {"Иван", null, "Анна"};
// Arrays.sort(names);  // NullPointerException!
// Решение: используем компаратор с обработкой null
Arrays.sort(names, Comparator.nullsLast(String::compareTo));

Лучшие практики и советы профессионалов

1. Используйте встроенные методы

Не пишите свои алгоритмы сортировки, если это не учебная задача. Arrays.sort() и Collections.sort() оптимизированы лучше, чем любой ручной код.

Золотое правило: 99% времени используйте встроенную сортировку. Свои алгоритмы пишите только для обучения или если нужна специфическая логика.

2. Выбирайте правильный алгоритм под задачу

Ситуация	Рекомендуемый алгоритм
Маленький массив (до 50 элементов)	Сортировка вставками
Большой массив примитивов	Arrays.sort() (быстрая сортировка)
Большой массив объектов	Collections.sort() (Timsort)
Почти отсортированные данные	Сортировка вставками
Нужна стабильность	Сортировка слиянием или Timsort

3. Используйте лямбды и Stream API

Современный Java-код должен использовать функциональный стиль. Это короче и читаемее.

// Старый стиль (не рекомендуется)
Collections.sort(students, new Comparator<Student>() {
    @Override
    public int compare(Student s1, Student s2) {
        return Integer.compare(s1.grade, s2.grade);
    }
});

// Новый стиль (рекомендуется)
students.sort(Comparator.comparingInt(s -> s.grade));

4. Сортируйте только то, что нужно

Не сортируйте весь массив, если нужны только первые 10 элементов. Используйте частичную сортировку или PriorityQueue.

5. Тестируйте на граничных случаях

Всегда проверяйте:

• Пустой массив
• Массив из одного элемента
• Массив с одинаковыми элементами
• Массив с null значениями
• Массив, уже отсортированный в обратном порядке

Вопросы для самопроверки

1. Что такое стабильная сортировка и почему это важно?
   Ответ: Стабильная сортировка сохраняет относительный порядок равных элементов. Это важно, когда мы сортируем по нескольким полям: сначала по одному, потом по другому.
2. Какая сложность у пузырьковой сортировки в лучшем и худшем случае?
   Ответ: В лучшем случае (массив уже отсортирован) — O(n), если добавить оптимизацию с флагом. В худшем — O(n²).
3. Почему Arrays.sort() для примитивов использует быструю сортировку, а для объектов — Timsort?
   Ответ: Для примитивов не нужна стабильность, быстрая сортировка быстрее и использует меньше памяти. Для объектов нужна стабильность, Timsort её обеспечивает.
4. Как отсортировать массив строк в обратном алфавитном порядке?
   Ответ: Arrays.sort(strings, Collections.reverseOrder());
5. Что произойдёт, если в массиве есть null при сортировке?
   Ответ: Будет выброшено исключение NullPointerException. Нужно использовать компаратор с обработкой null: Comparator.nullsLast() или Comparator.nullsFirst().
6. В чём разница между Comparable и Comparator?
   Ответ: Comparable — это естественный порядок сортировки, определённый в самом классе (метод compareTo). Comparator — это внешний компаратор, который можно передать в метод sort для изменения порядка.
7. Какой алгоритм сортировки использует Python по умолчанию?
   Ответ: Timsort — гибрид сортировки слиянием и сортировки вставками. Сложность O(n log n) в худшем случае.
8. Можно ли отсортировать HashMap?
   Ответ: HashMap по определению неупорядочен. Можно отсортировать ключи или значения, сохранив их в TreeMap или ArrayList.
9. Что такое "большой O" и как его считать для сортировки? <