Рубрики
Без рубрики

Сортировка на Java

Практическое введение в сортировку на Java.

Автор оригинала: baeldung.

1. Обзор

Эта статья будет иллюстрировать, как применить сортировку к Массив , Список , Установить и Карта на Java 7 и Java 8.

2. Сортировка с array

Начнем с сортировки целых массивов сначала с помощью Arrays.sort () метод.

Мы определим следующие int массивы в @Before jUnit метод:

@Before
public void initVariables () {
    toSort = new int[] 
      { 5, 1, 89, 255, 7, 88, 200, 123, 66 }; 
    sortedInts = new int[] 
      {1, 5, 7, 66, 88, 89, 123, 200, 255};
    sortedRangeInts = new int[] 
      {5, 1, 89, 7, 88, 200, 255, 123, 66};
    ...
}

2.1. Сортировка полного массива

Теперь давайте использовать простую Array.sort () API:

@Test
public void givenIntArray_whenUsingSort_thenSortedArray() {
    Arrays.sort(toSort);

    assertTrue(Arrays.equals(toSort, sortedInts));
}

Несортированный массив теперь полностью отсортирован:

[1, 5, 7, 66, 88, 89, 123, 200, 255]

Как уже упоминалось в официальном JavaDoc , Arrays.sort использует двойной поворот Квиксорт на примитивы . Он обеспечивает производительность O (n log(n)) и, как правило, быстрее, чем традиционные (односторонные) реализации quicksort. Тем не менее, он использует стабильную, адаптивную, итеративную реализацию алгоритм mergesort для Массив объектов .

2.2. Сортировка части массива

Arrays.sort имеет еще одну сортировать API – которые мы обсудим здесь:

Arrays.sort(int[] a, int fromIndex, int toIndex)

Это позволит сортировать только часть массива между двумя индексами.

Рассмотрим быстрый пример:

@Test
public void givenIntArray_whenUsingRangeSort_thenRangeSortedArray() {
    Arrays.sort(toSort, 3, 7);
 
    assertTrue(Arrays.equals(toSort, sortedRangeInts));
}

Сортировка будет происходить только на следующих подразрядных элементах ( в “Яндекс будет эксклюзивной):

[255, 7, 88, 200]

В результате отсортированная под массивная включительно с основным массивом будет:

[5, 1, 89, 7, 88, 200, 255, 123, 66]

2.3. Java 8 Arrays.sort против Arrays.parallelSort

Java 8 поставляется с новым API – parallelSort – с аналогичной подписью к Arrays.sort () API:

@Test 
public void givenIntArray_whenUsingParallelSort_thenArraySorted() {
    Arrays.parallelSort(toSort);
 
    assertTrue(Arrays.equals(toSort, sortedInts));
}

За кулисами parallelSort(), он разбивает массив на различные подразряды (в соответствии с детализацией в алгоритме parallelSort ). Каждый подразряд отсортирован с Arrays.sort () в разных потоках, так что сортировать могут быть выполнены параллельно и объединены, наконец, как отсортированы массива.

Обратите внимание, что ForJoin общий бассейн используется для выполнения этих параллельных задач, а затем слияния результатов.

Результат Arrays.parallelSort будет таким же, как Array.sort Конечно, это просто вопрос использования многотысяй.

Наконец, существуют аналогичные варианты API Arrays.sort в Arrays.parallelSort тоже:

Arrays.parallelSort (int [] a, int fromIndex, int toIndex);

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

Давайте теперь использовать Коллекции.сорт () API в java.utils.Collections – разобраться в Список из интеграторов:

@Test
public void givenList_whenUsingSort_thenSortedList() {
    List toSortList = Ints.asList(toSort);
    Collections.sort(toSortList);

    assertTrue(Arrays.equals(toSortList.toArray(), 
    ArrayUtils.toObject(sortedInts)));
}

Список перед сортировкой будет содержать следующие элементы:

[5, 1, 89, 255, 7, 88, 200, 123, 66]

И, естественно, после сортировки:

[1, 5, 7, 66, 88, 89, 123, 200, 255]

Как уже упоминалось в Oracle JavaDoc для Коллекции.Сортировка , он использует модифицированный mergesort и предлагает гарантированные n журнал (n) производительность.

4. Сортировка набора

Далее, давайте использовать Коллекции.сорт () сортировать LinkedHashSet .

Мы используем LinkedHashSet потому что он поддерживает порядок вставки.

Обратите внимание, как, для того, чтобы использовать сортировать API в Коллекции – мы впервые обертывание набора в список :

@Test
public void givenSet_whenUsingSort_thenSortedSet() {
    Set integersSet = new LinkedHashSet<>(Ints.asList(toSort));
    Set descSortedIntegersSet = new LinkedHashSet<>(
      Arrays.asList(new Integer[] 
        {255, 200, 123, 89, 88, 66, 7, 5, 1}));
        
    List list = new ArrayList(integersSet);
    Collections.sort(Comparator.reverseOrder());
    integersSet = new LinkedHashSet<>(list);
        
    assertTrue(Arrays.equals(
      integersSet.toArray(), descSortedIntegersSet.toArray()));
}

Comparator.reverseOrder() метод меняет порядок, навязанный естественным заказом.

5. Сортировка карты

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

Давайте сначала определим карту, которую мы будем сортировать:

@Before
public void initVariables () {
    ....
    HashMap map = new HashMap<>();
    map.put(55, "John");
    map.put(22, "Apple");
    map.put(66, "Earl");
    map.put(77, "Pearl");
    map.put(12, "George");
    map.put(6, "Rocky");
    ....
}

5.1. Сортировка карты по ключам

Теперь мы добым ключи и значения записи из HashMap и сортировать его на основе значений ключей в этом примере:

@Test
public void givenMap_whenSortingByKeys_thenSortedMap() {
    Integer[] sortedKeys = new Integer[] { 6, 12, 22, 55, 66, 77 };

    List> entries 
      = new ArrayList<>(map.entrySet());
    Collections.sort(entries, new Comparator>() {
        @Override
        public int compare(
          Entry o1, Entry o2) {
            return o1.getKey().compareTo(o2.getKey());
        }
    });
    Map sortedMap = new LinkedHashMap<>();
    for (Map.Entry entry : entries) {
        sortedMap.put(entry.getKey(), entry.getValue());
    }
        
    assertTrue(Arrays.equals(sortedMap.keySet().toArray(), sortedKeys));
}

Обратите внимание, как мы использовали LinkedHashMap при копировании отсортированного Записи на основе ключей (потому что HashSet не гарантирует порядок ключей).

Карта перед сортировкой:

[Key: 66 , Value: Earl] 
[Key: 22 , Value: Apple] 
[Key: 6 , Value: Rocky] 
[Key: 55 , Value: John] 
[Key: 12 , Value: George] 
[Key: 77 , Value: Pearl]

Карта после сортировки по клавишам :

[Key: 6 , Value: Rocky] 
[Key: 12 , Value: George] 
[Key: 22 , Value: Apple] 
[Key: 55 , Value: John] 
[Key: 66 , Value: Earl] 
[Key: 77 , Value: Pearl]

5.2. Сортировка карты по значениям

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

@Test
public void givenMap_whenSortingByValues_thenSortedMap() {
    String[] sortedValues = new String[] 
      { "Apple", "Earl", "George", "John", "Pearl", "Rocky" };

    List> entries 
      = new ArrayList<>(map.entrySet());
    Collections.sort(entries, new Comparator>() {
        @Override
        public int compare(
          Entry o1, Entry o2) {
            return o1.getValue().compareTo(o2.getValue());
        }
    });
    Map sortedMap = new LinkedHashMap<>();
    for (Map.Entry entry : entries) {
        sortedMap.put(entry.getKey(), entry.getValue());
    }
        
    assertTrue(Arrays.equals(sortedMap.values().toArray(), sortedValues));
}

Карта перед сортировкой:

[Key: 66 , Value: Earl] 
[Key: 22 , Value: Apple] 
[Key: 6 , Value: Rocky] 
[Key: 55 , Value: John] 
[Key: 12 , Value: George] 
[Key: 77 , Value: Pearl]

Карта после сортировки значениями :

[Key: 22 , Value: Apple] 
[Key: 66 , Value: Earl] 
[Key: 12 , Value: George] 
[Key: 55 , Value: John] 
[Key: 77 , Value: Pearl] 
[Key: 6 , Value: Rocky]

6. Сортировка пользовательских объектов

Теперь давайте работать с пользовательским объектом:

public class Employee implements Comparable {
    private String name;
    private int age;
    private double salary;

    public Employee(String name, int age, double salary) {
        ...
    }

    // standard getters, setters and toString
}

Мы будем использовать следующие Сотрудник Array для сортировки примера в следующих разделах:

@Before
public void initVariables () {
    ....    
    employees = new Employee[] { 
      new Employee("John", 23, 5000), new Employee("Steve", 26, 6000), 
      new Employee("Frank", 33, 7000), new Employee("Earl", 43, 10000), 
      new Employee("Jessica", 23, 4000), new Employee("Pearl", 33, 6000)};
    
    employeesSorted = new Employee[] {
      new Employee("Earl", 43, 10000), new Employee("Frank", 33, 70000),
      new Employee("Jessica", 23, 4000), new Employee("John", 23, 5000), 
      new Employee("Pearl", 33, 4000), new Employee("Steve", 26, 6000)};
    
    employeesSortedByAge = new Employee[] { 
      new Employee("John", 23, 5000), new Employee("Jessica", 23, 4000), 
      new Employee("Steve", 26, 6000), new Employee("Frank", 33, 70000), 
      new Employee("Pearl", 33, 4000), new Employee("Earl", 43, 10000)};
}

Мы можем сортировать массивы или коллекции пользовательских объектов либо:

  1. в естественном порядке (Использование Сопоставимые Интерфейс) или
  2. в порядке, предоставленном Компаратор интерфейс

6.1. Использование сопоставимых

Естественный порядок в Java означает порядок упорядоченной сортировки примитивных или объектов в данном массиве или коллекции.

Оба java.util.Arrays и java.util.Collections иметь сортировать () метод и Настоятельно рекомендуется, чтобы естественные заказы соответствовали семантике равняется .

В этом примере мы рассмотрим сотрудников с таким же имя на равных:

@Test
public void givenEmpArray_SortEmpArray_thenSortedArrayinNaturalOrder() {
    Arrays.sort(employees);

    assertTrue(Arrays.equals(employees, employeesSorted));
}

Естественный порядок элементов можно определить, реализуя Сопоставимые интерфейс, который имеет сравнитьTo() метод сравнения текущего объекта и объекта, пройденный в качестве аргумента.

Чтобы понять это ясно, давайте посмотрим пример Сотрудник класс, который реализует Сопоставимые интерфейс:

public class Employee implements Comparable {
    ...

    @Override
    public boolean equals(Object obj) {
        return ((Employee) obj).getName().equals(getName());
    }

    @Override
    public int compareTo(Object o) {
        Employee e = (Employee) o;
        return getName().compareTo(e.getName());
    }
}

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

Теперь, когда Arrays.sort (сотрудники); называется в вышеупомянутом коде, теперь мы знаем, что такое логика и порядок, который идет в сортировке сотрудников в соответствии с возрастом:

[("Earl", 43, 10000),("Frank", 33, 70000), ("Jessica", 23, 4000),
 ("John", 23, 5000),("Pearl", 33, 4000), ("Steve", 26, 6000)]

Мы видим, массив сортируются по имени сотрудника – который теперь становится естественным заказом для Сотрудник класс.

6.2. Использование компаратора

Теперь давайте разберем элементы с помощью Компаратор реализация интерфейса – где мы перемахим анонимный внутренний класс на лету в Arrays.sort () API:

@Test
public void givenIntegerArray_whenUsingSort_thenSortedArray() {
    Integer [] integers = ArrayUtils.toObject(toSort);
    Arrays.sort(integers, new Comparator() {
        @Override
        public int compare(Integer a, Integer b) {
            return Integer.compare(a, b);
        }
    });
 
    assertTrue(Arrays.equals(integers, ArrayUtils.toObject(sortedInts)));
}

Теперь позволяет сортировать сотрудников на основе зарплата – и пройти в другой реализации компаратора:

Arrays.sort(employees, new Comparator() {
    @Override
    public int compare(Employee o1, Employee o2) {
       return Double.compare(o1.getSalary(), o2.getSalary());
    }
 });

Отсортированные массивы сотрудников на основе зарплата будет:

[(Jessica,23,4000.0), (John,23,5000.0), (Pearl,33,6000.0), (Steve,26,6000.0), 
(Frank,33,7000.0), (Earl,43,10000.0)]

Обратите внимание, что мы можем использовать Коллекции.сорт () аналогичным образом, чтобы сортировать Список и Установить объектов в естественном или пользовательском порядке, как описано выше для Arrays.

7. Сортировка с Ламбдасом

Начнем с Java 8, мы можем использовать Lambdas для реализации Компаратор Функциональный интерфейс.

Вы можете взглянуть на Lambdas в Java 8 writeup, чтобы освежить синтаксис.

Давайте заменим старый компаратор:

Comparator c  = new Comparator<>() {
    @Override
    public int compare(Integer a, Integer b) {
        return Integer.compare(a, b);
    }
}

При эквивалентной реализации, используя выражение Lambda:

Comparator c = (a, b) -> Integer.compare(a, b);

Наконец, давайте напишем тест:

@Test
public void givenArray_whenUsingSortWithLambdas_thenSortedArray() {
    Integer [] integersToSort = ArrayUtils.toObject(toSort);
    Arrays.sort(integersToSort, (a, b) -> {
        return Integer.compare(a, b);
    });
 
    assertTrue(Arrays.equals(integersToSort, 
      ArrayUtils.toObject(sortedInts)));
}

Как вы можете видеть, гораздо чище и более краткая логика здесь.

8. Использование Comparator.comparing и Comparator.thenСовместив

Java 8 поставляется с двумя новыми API, полезными для сортировки – сравнение () и затемСовместив () в Компаратор интерфейс.

Они очень удобны для цепочки нескольких условий Компаратор .

Рассмотрим сценарий, в котором мы можем сравнить Сотрудник по возрастные а затем имя :

@Test
public void givenArrayObjects_whenUsingComparing_thenSortedArrayObjects() {
    List employeesList = Arrays.asList(employees);
    employees.sort(Comparator.comparing(Employee::getAge));

    assertTrue(Arrays.toString(employees.toArray())
      .equals(sortedArrayString));
}

В этом примере Сотрудник::getAge является ключом сортировки для Компаратор интерфейс реализации функционального интерфейса с функцией сравнения.

Вот массив сотрудников после сортировки:

[(John,23,5000.0), (Jessica,23,4000.0), (Steve,26,6000.0), (Frank,33,7000.0), 
(Pearl,33,6000.0), (Earl,43,10000.0)]

Здесь сотрудники сортируются на основе возрастные .

Мы можем видеть Джон и Джессика того же возраста – а это означает, что логика порядка должна теперь принимать их имена во внимание, которые мы можем достичь с затемСовместив () :

... 
employees.sort(Comparator.comparing(Employee::getAge)
  .thenComparing(Employee::getName)); 
...

После сортировки с вышеуказанным фрагментом кода элементы массива сотрудников будут отсортированы как:

[(Jessica,23,4000.0), 
 (John,23,5000.0), 
 (Steve,26,6000.0), 
 (Frank,33,7000.0), 
 (Pearl,33,6000.0), 
 (Earl,43,10000.0)
]

Таким сравнение () и затемСовместив () определенно сделать более сложные сценарии сортировки намного чище для реализации.

9. Заключение

В этой статье мы увидели, как мы можем применить сортировку к Массив , Список , Установить , и Карта .

Мы также увидели краткое введение о том, как функции Java 8 могут быть полезны в сортировке, как использование Lambdas, сравнение () и затемСовместив () и parallelSort () .

Все примеры, используемые в статье, доступны более на GitHub .

Читайте ещё по теме: