Перейти к основному содержимому

Сортировка массивов в Java

· 4 мин. чтения

Задача: Сумма двух чисел

Напишите функцию twoSum. Которая получает массив целых чисел nums и целую сумму target, а возвращает индексы двух чисел, сумма которых равна target. Любой набор входных данных имеет ровно одно решение, и вы не можете использовать один и тот же элемент дважды. Ответ можно возвращать в любом порядке...

ANDROMEDA

1. Обзор

В этом руководстве мы обсудим распространенные методы сортировки массивов в порядке возрастания и убывания.

Мы рассмотрим использование метода сортировки класса Arrays в Java, а также реализацию нашего собственного компаратора для упорядочения значений наших массивов.

2. Определения объектов

Прежде чем мы начнем, давайте быстро определим несколько массивов, которые мы будем сортировать в этом руководстве. Во-первых, мы создадим массив целых чисел и массив строк:

int[] numbers = new int[] { -8, 7, 5, 9, 10, -2, 3 };
String[] strings = new String[] { "learning", "java", "with", "foreach" };

И давайте также создадим массив объектов Employee , где у каждого сотрудника есть атрибут id и name :

Employee john = new Employee(6, "John");
Employee mary = new Employee(3, "Mary");
Employee david = new Employee(4, "David");
Employee[] employees = new Employee[] { john, mary, david };

3. Сортировка по возрастанию

Метод Java util.Arrays.sort предоставляет нам быстрый и простой способ сортировки массива примитивов или объектов, реализующих интерфейс Comparable , в порядке возрастания.

При сортировке примитивов метод Arrays.sort использует реализацию быстрой сортировки Dual- Pivot . Однако при сортировке объектов используется итеративная реализация MergeSort .

3.1. примитивы

Чтобы отсортировать примитивный массив в порядке возрастания, мы передаем наш массив методу sort :

Arrays.sort(numbers);
assertArrayEquals(new int[] { -8, -2, 3, 5, 7, 9, 10 }, numbers);

3.2. Объекты, реализующие Comparable

Для объектов, которые реализуют интерфейс Comparable , как и в случае с нашим примитивным массивом, мы также можем просто передать наш массив методу сортировки :

Arrays.sort(strings);
assertArrayEquals(new String[] { "foreach", "java", "learning", "with" }, strings);

3.3. Объекты, которые не реализуют Comparable

Сортировка объектов, не реализующих Comparable Interface, таких как наш массив Employees , требует, чтобы мы указали собственный компаратор.

Мы можем сделать это очень легко в Java 8, указав свойство, по которому мы хотели бы сравнить наши объекты Employee в нашем Comparator:

Arrays.sort(employees, Comparator.comparing(Employee::getName));
assertArrayEquals(new Employee[] { david, john, mary }, employees);

В этом случае мы указали, что хотели бы упорядочить наших сотрудников по атрибутам их имен .

Мы также можем сортировать наши объекты по более чем одному атрибуту, объединяя наши сравнения с помощью метода thenComparing компаратора :

Arrays.sort(employees, Comparator.comparing(Employee::getName).thenComparing(Employee::getId));

4. Сортировка по убыванию

4.1. примитивы

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

Во- первых, мы могли бы отсортировать наш массив в порядке возрастания, а затем выполнить реверсирование массива на месте.

Во- вторых, можно преобразовать наш массив в список, использовать метод Guava Lists.reverse() , а затем преобразовать наш список обратно в массив.

Наконец, мы можем преобразовать наш массив в поток , а затем отобразить его обратно в массив int . У него есть приятное преимущество в том , что он однострочный и использует только ядро Java:

numbers = IntStream.of(numbers).boxed().sorted(Comparator.reverseOrder()).mapToInt(i -> i).toArray();
assertArrayEquals(new int[] { 10, 9, 7, 5, 3, -2, -8 }, numbers);

Причина, по которой это работает, заключается в том, что boxed превращает каждый int в Integer , который реализует компаратор.

4.2. Объекты, реализующие Comparable

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

В Java 8 мы можем использовать Comparator.reverseOrder() , чтобы указать, что мы хотим, чтобы наш массив был отсортирован в порядке убывания:

Arrays.sort(strings, Comparator.reverseOrder());
assertArrayEquals(new String[] { "with", "learning", "java", "foreach" }, strings);

4.3. Объекты, которые не реализуют Comparable

Подобно сортировке объектов, которые реализуют сопоставимость, мы можем изменить порядок нашего пользовательского компаратора , добавив reversed() в конце нашего определения сравнения:

Arrays.sort(employees, Comparator.comparing(Employee::getName).reversed());
assertArrayEquals(new Employee[] { mary, john, david }, employees);

5. Вывод

В этой статье мы обсудили, как сортировать массивы примитивов и объектов по возрастанию и убыванию с помощью метода Arrays.sort .

Как обычно, исходный код из этой статьи можно найти на Github .