Сортировка коллекций Java

Сортировка коллекции Java выполняется через три идиоматических метода: Collections.sort(list), list.sort(comparator) и stream.sorted(). Все три используют один и тот же алгоритм — стабильный адаптивный mergesort (вариант TimSort) со сложностью O(n log n) в худшем случае — и одну и ту же зависимость: либо тип элемента реализует Comparable, либо вы передаёте Comparator. Различия — в том, где хранится результат и как выглядит вызов.

Эта глава посвящена спискам. Множества и отображения имеют собственные способы поддержания порядка (TreeSet, TreeMap) — они сортируют при вставке, а не после неё. Если у вас есть HashSet, который нужно отсортировать, стандартный шаблон — new ArrayList<>(set) с последующей сортировкой.

Три точки входа

Collections.sort(list) — исходный метод

Collections.sort(list);                  // natural ordering — list element type must implement Comparable
Collections.sort(list, comparator);       // explicit comparator

Сортирует на месте. Стабильный. Возвращает void. Появился до Java 8 и по-прежнему широко используется: вызов очевиден, а альтернатив тогда не существовало. На современных JDK делегирует к list.sort внутри.

list.sort(comparator) — современный метод экземпляра

list.sort(null);                          // natural ordering — null means "use Comparable"
list.sort(comparator);

Добавлен в Java 8 непосредственно в List<E>. Семантика та же, что у Collections.sort — на месте, стабильный, возвращает void. Метод экземпляра позволяет реализации списка переопределить алгоритм, если это выгодно (например, LinkedList этого не делает, но пользовательский список мог бы).

Используйте list.sort в новом коде. Он короче, лучше читается с ссылками на методы и не требует импорта Collections.

stream.sorted() — когда нужна новая последовательность

List<Person> sorted = people.stream()
                            .sorted(Comparator.comparingInt(Person::age))
                            .toList();

Возвращает новый отсортированный поток — входные данные остаются нетронутыми. Используйте этот метод, когда:

• Входной список неизменяем (List.of(...)), и list.sort выбросит исключение.
• Вы всё равно строите конвейер (map, filter, затем sort).
• Вы не хотите изменять исходный список.

Стоимость — дополнительное выделение памяти для отсортированного результата. Для коротких списков это несущественно; для списка из миллиона элементов Collections.sort, изменяющий список на месте, дешевле, чем stream().sorted().toList(), копирующий весь список.

Естественный порядок и компаратор

Оба метода Collections.sort(list) и list.sort(null) используют естественный порядок типа элемента, определяемый его реализацией Comparable:

List<String> names = new ArrayList<>(List.of("carol", "alice", "bob"));
names.sort(null);                        // [alice, bob, carol]

Если тип элемента не реализует Comparable, во время выполнения возникнет ClassCastException — не ошибка компиляции, потому что приведение происходит внутри сортировки. Чтобы это исправить, передайте Comparator явно:

List<Person> people = new ArrayList<>(...);
people.sort(Comparator.comparing(Person::name));

Подходит любой Comparator из предыдущей главы — одиночный ключ, составные ключи, реверс, обработка null и всё остальное.

Стабильная сортировка: равные элементы сохраняют порядок

TimSort стабилен: если два элемента равны по компаратору, тот, что стоял первым на входе, окажется первым и на выходе. Это позволяет реализовать многоключевую сортировку в виде последовательных однокюлчевых проходов:

people.sort(Comparator.comparing(Person::lastName));     // first pass
people.sort(Comparator.comparingInt(Person::age));        // second pass — primary key wins, ties broken by previous order

После обоих проходов список отсортирован прежде всего по age, а внутри каждой возрастной группы — по lastName. Сортировка в обратном порядке приоритетов — сначала вторичный ключ, последним — первичный — это приём, делающий многопроходную сортировку рабочей. В большинстве случаев лучше написать составной компаратор из предыдущей главы; это устаревшая альтернатива.

Изменяемые и неизменяемые списки

List.of(...), Collections.unmodifiableList(...) и Arrays.asList(array) возвращают списки, которые нельзя сортировать на месте. list.sort(...) внутри вызывает list.set(i, x), а неизменяемые списки бросают UnsupportedOperationException из этого метода.

Два способа исправить:

List<String> sorted = original.stream().sorted().toList();   // new immutable, sorted list
List<String> copy   = new ArrayList<>(original); copy.sort(null);

Arrays.asList(...) — особый случай: список фиксированного размера, но ячейки изменяемы, поэтому sort работает. add/remove — нет.

Примитивные списки и налог на боксинг

List<Integer> упаковывает каждое значение. Сортировка миллиона Integer намного медленнее, чем сортировка int[]. Если данные примитивны, предпочитайте:

int[] data = ...;
Arrays.sort(data);                       // primitive sort: cache-friendly, no boxing

…и преобразуйте в список, если он понадобится позже. То же применимо к long[], double[], char[]. Если вы сортируете по примитивному ключу объектов, используйте Comparator.comparingInt, comparingLong, comparingDouble, чтобы избежать боксинга внутри компаратора:

people.sort(Comparator.comparingInt(Person::age));     // unboxed key extraction

Collections.sort изменяет список на месте; иногда нужна копия

Если вы хотите получить отсортированный результат без изменения источника:

List<String> sortedCopy = new ArrayList<>(source);
sortedCopy.sort(null);

…или в виде потока:

List<String> sortedCopy = source.stream().sorted().toList();

Оба варианта работают. Первый — две строки без накладных расходов конвейера. Второй — одно выражение. Выбирайте то, что лучше вписывается в окружающий код.

Сортировка Map по значению

У отображений нет метода sort — у Map нет понятия «позиция». Идиома — отсортировать набор записей в List и затем итерировать его:

List<Map.Entry<String, Integer>> byCount = scores.entrySet().stream()
    .sorted(Map.Entry.<String, Integer>comparingByValue().reversed())
    .toList();

Если результат должен быть отображением с сохранённым порядком итерации, собирайте в LinkedHashMap — его порядок вставки является порядком итерации:

LinkedHashMap<String, Integer> ordered = scores.entrySet().stream()
    .sorted(Map.Entry.<String, Integer>comparingByValue().reversed())
    .collect(Collectors.toMap(
        Map.Entry::getKey, Map.Entry::getValue,
        (a, b) -> a, LinkedHashMap::new));

Четырёхаргументный вариант toMap позволяет выбрать реализацию отображения. Не пропускайте его — по умолчанию используется HashMap, который уничтожает только что установленный порядок.

Пример: сортировка на месте, сортировка через поток, составной компаратор и сортировка отображения

Программа ниже сортирует список на месте, строит отсортированную копию с помощью stream().sorted(), применяет составной компаратор с обратным вторичным ключом, а затем сортирует отображение по значению в LinkedHashMap, сохраняющий отсортированный порядок при итерации.

Что следует вынести из запуска:

• Сортировка на месте применила составной компаратор и за один вызов получила порядок по возрасту (по возрастанию) с тай-брейкером по зарплате (по убыванию). Второй проход не понадобился.
• Потоковый вариант вернул новый отсортированный список и оставил исходный List.of нетронутым. Это правильный шаблон, когда входные данные неизменяемы или разделяются.
• Вызов sort на неизменяемом списке бросил UnsupportedOperationException. Сортировка выполняется на месте, а «на месте» требует изменяемости.
• Ранжирование отображения записалось в LinkedHashMap, поэтому его итерация совпадает с порядком сортировки. Если бы мы использовали трёхаргументный toMap, результатом был бы HashMap и порядок был бы потерян.

Что дальше

Теперь вы умеете упорядочивать любой список и создавать отсортированную копию без изменения источника. Следующая операция — поиск: нахождение элемента по предикату, по равенству или бинарным поиском в уже отсортированном списке. Следующая глава: Поиск в коллекциях Java.

Практика