Сортировка массивов в Java: Arrays.sort и Comparator

Сортировка — одна из тех операций, к которым вы будете обращаться постоянно, и стандартная библиотека Java делает её однострочной — в большинстве случаев. Загвоздка в том, что тип элемента имеет значение: примитивы сортируются одним способом, объекты — другим, а «хочу убывающий порядок» или «сортировать по полю» требует Comparator. В этой главе рассмотрено всё это.

Ключевой метод — Arrays.sort. Он сортирует на месте — то есть изменяет переданный массив. Если вы хотите сохранить оригинал, сначала скопируйте его.

Сортировка примитивов

Для int[], long[], double[], char[] и других достаточно одного вызова:

import java.util.Arrays;

int[] data = {3, 1, 4, 1, 5, 9, 2, 6};
Arrays.sort(data);
System.out.println(Arrays.toString(data));   // [1, 1, 2, 3, 4, 5, 6, 9]

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

Чтобы отсортировать по убыванию, можно упаковать в Integer[] и передать компаратор, либо отсортировать по возрастанию и перевернуть вручную:

int[] data = {3, 1, 4};
Arrays.sort(data);
// reverse in place
for (int i = 0, j = data.length - 1; i < j; i++, j--) {
  int tmp = data[i]; data[i] = data[j]; data[j] = tmp;
}

Сортировка диапазона

Передайте from (включительно) и to (не включая) для сортировки только части массива:

int[] data = {9, 8, 7, 6, 5, 4, 3, 2, 1};
Arrays.sort(data, 2, 6);
// {9, 8, 4, 5, 6, 7, 3, 2, 1} — only positions 2..5 sorted

Элементы за пределами диапазона остаются на своих местах.

Сортировка объектных массивов (естественный порядок)

Для массива объектов, класс которых реализует Comparable<T> — String, упакованные числовые обёртки, LocalDate, всё что имеет «естественный» порядок — вызывайте Arrays.sort напрямую:

String[] words = {"banana", "apple", "cherry"};
Arrays.sort(words);
// {"apple", "banana", "cherry"} — alphabetical

Если класс не реализует Comparable, во время выполнения выбрасывается ClassCastException. Решение — передать Comparator.

Сортировка с `Comparator`

Comparator<T> — это функция, которая, получив два объекта T, возвращает отрицательное число, ноль или положительное число, означающие «первый меньше», «равны», «первый больше». Самый удобный способ создать его — использовать Comparator.comparing:

record Player(String name, int score) {}

Player[] players = {
  new Player("Ada", 1500),
  new Player("Linus", 1800),
  new Player("Grace", 1650)
};

// sort by score, ascending
Arrays.sort(players, Comparator.comparing(Player::score));

// sort by score, descending
Arrays.sort(players, Comparator.comparing(Player::score).reversed());

// sort by name (case-insensitive), then by score as tiebreaker
Arrays.sort(players,
  Comparator.comparing(Player::name, String.CASE_INSENSITIVE_ORDER)
            .thenComparing(Player::score));

Цепочка Comparator.comparing(...).reversed() и .thenComparing(...) — идиоматический способ составлять порядки сортировки. Писать класс-компаратор вручную почти никогда не нужно. Для более детального рассмотрения разницы между естественным порядком класса и внешним Comparator см. Comparable vs Comparator.

Обработка null-элементов

Обычный компаратор выбрасывает NullPointerException, если массив содержит null. Оберните его в Comparator.nullsFirst или Comparator.nullsLast, чтобы переместить null в начало или конец:

String[] words = {"banana", null, "apple"};
Arrays.sort(words, Comparator.nullsFirst(Comparator.naturalOrder()));
// {null, "apple", "banana"}

Сортировка упакованных примитивов

Integer[], Double[] и другие — это объектные массивы, поэтому весь механизм Comparator доступен:

Integer[] nums = {3, 1, 4, 1, 5};
Arrays.sort(nums, Comparator.reverseOrder());
// {5, 4, 3, 1, 1}

Если нужен убывающий порядок для примитивного массива, упаковка — наиболее чистый путь, при условии что массив не слишком большой.

Стабильность

Стабильность сортировки означает, что равные элементы сохраняют исходный относительный порядок. Объектная сортировка в Java стабильна: если два Player имеют одинаковый счёт, тот, кто шёл первым, останется первым. Сортировка примитивов не гарантированно стабильна, но поскольку примитивы не имеют идентичности помимо своего значения, этого не заметить.

Это важно при последовательных сортировках — например, сначала по счёту, затем по имени. Со стабильной сортировкой второй проход сохраняет порядок первого там, где новый ключ совпадает. При использовании thenComparing оба ключа объединяются в один компаратор, что обычно является более чистым подходом.

`parallelSort`

Для очень больших массивов Arrays.parallelSort распределяет работу по нескольким потокам:

int[] huge = new int[10_000_000];
// ... fill huge ...
Arrays.parallelSort(huge);

Тот же API, та же семантика изменения на месте. Создание потоков требует накладных расходов, поэтому для маленьких массивов обычный sort быстрее. Порог находится в районе десятков тысяч элементов; ниже него не стоит использовать parallelSort.

Если ваши данные хранятся в List, а не в массиве, аналогом является Collections.sort или list.sort(...) — те же правила компараторов применяются. См. как сортировать ArrayList.

Практический пример

java— editable, runs on the server

import java.util.Arrays;
import java.util.Comparator;

public class SortingDemo {
  record Player(String name, int score) {}

public static void main(String[] args) {
    // 1. primitive ascending
    int[] nums = {3, 1, 4, 1, 5, 9, 2, 6};
    Arrays.sort(nums);
    System.out.println("sorted ints:  " + Arrays.toString(nums));

// 2. partial sort
    int[] partial = {9, 8, 7, 6, 5, 4, 3, 2, 1};
    Arrays.sort(partial, 2, 6);
    System.out.println("partial:       " + Arrays.toString(partial));

// 3. Strings — natural order
    String[] words = {"banana", "apple", "cherry"};
    Arrays.sort(words);
    System.out.println("sorted words: " + Arrays.toString(words));

// 4. boxed descending
    Integer[] desc = {3, 1, 4, 1, 5};
    Arrays.sort(desc, Comparator.reverseOrder());
    System.out.println("descending:   " + Arrays.toString(desc));

// 5. objects by field
    Player[] players = {
      new Player("Ada", 1500),
      new Player("Linus", 1800),
      new Player("Grace", 1650),
      new Player("Ada", 1700)
    };

Arrays.sort(players, Comparator.comparing(Player::score).reversed());
    System.out.println("by score desc:");
    for (Player p : players) System.out.println("  " + p);

Arrays.sort(players,
      Comparator.comparing(Player::name).thenComparing(Player::score));
    System.out.println("by name then score:");
    for (Player p : players) System.out.println("  " + p);
  }
}

Что дальше

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

Практика

Как отсортировать int[] по убыванию?

Отсортировать по возрастанию и перевернуть, или упаковать в Integer[] и использовать Comparator.reverseOrder()Arrays.sort(array, Comparator.reverseOrder())Arrays.sort(array, false)Arrays.sortDescending(array)