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

Проверка сортировки массива в Java

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

1. Обзор​

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

Однако перед началом было бы интересно проверить , как сортировать массивы в Java .

2. С петлей​

Один из способов проверки — цикл for . Мы можем перебирать все значения массива одно за другим.

Давайте посмотрим, как это сделать.

2.1. Примитивный массив​

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

Если какие-то из них не отсортированы, метод вернет false. Если ни одно из сравнений не возвращает false, это означает, что массив отсортирован:

boolean isSorted(int[] array) {
    for (int i = 0; i < array.length - 1; i++) {
        if (array[i] > array[i + 1])
            return false;
    }
    return true;
}

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

Мы можем сделать что-то подобное с объектами, которые реализуют Comparable. Вместо использования знака «больше» мы будем использовать compareTo :

boolean isSorted(Comparable[] array) {
    for (int i = 0; i < array.length - 1; ++i) {
        if (array[i].compareTo(array[i + 1]) > 0)
            return false;
    }
    return true;
}

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

Но что, если наши объекты не реализуют Comparable ? В этом случае мы можем вместо этого создать Comparator.

В этом примере мы будем использовать объект Employee . Это простой POJO с тремя полями:

public class Employee implements Serializable {
    private int id;
    private String name;
    private int age;

    // getters and setters
}

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

Comparator<Employee> byAge = Comparator.comparingInt(Employee::getAge);

И затем мы можем изменить наш метод, чтобы также использовать Comparator :

boolean isSorted(Object[] array, Comparator comparator) {
    for (int i = 0; i < array.length - 1; ++i) {
        if (comparator.compare(array[i], (array[i + 1])) > 0)
            return false;
    }

    return true;
}

3. Рекурсивно​

Вместо этого мы можем, конечно, использовать рекурсию . Идея здесь в том, что мы проверим две позиции в массиве, а затем рекурсивно проверим каждую позицию.

3.1. Примитивный массив​

В этом методе мы проверяем две последние позиции. Если они отсортированы, мы снова вызовем метод, но с предыдущей позицией. Если одна из этих позиций не отсортирована, метод вернет false:

boolean isSorted(int[] array, int length) {
    if (array == null || length < 2) 
        return true; 
    if (array[length - 2] > array[length - 1])
        return false;
    return isSorted(array, length - 1);
}

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

Теперь давайте снова посмотрим на объекты, реализующие Comparable. Мы увидим, что тот же подход с compareTo будет работать:

boolean isSorted(Comparable[] array, int length) {
    if (array == null || length < 2) 
        return true; 
    if (array[length - 2].compareTo(array[length - 1]) > 0)
        return false;
    return isSorted(array, length - 1);
}

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

Недавно давайте снова попробуем наш объект Employee , добавив параметр Comparator :

boolean isSorted(Object[] array, Comparator comparator, int length) {
    if (array == null || length < 2)
        return true;
    if (comparator.compare(array[length - 2], array[length - 1]) > 0)
        return false;
    return isSorted(array, comparator, length - 1);
}

4. Вывод​

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

Мы рекомендуем использовать циклическое решение. Он чище и легче читается.

Как обычно, исходный код из этого руководства можно найти на GitHub .