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

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. Вместо того, чтобы использовать знак больше, чем, мы будем использовать 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. Объекты, Которые Не Реализуют Сопоставимые

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

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

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

    // getters and setters
}

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

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

И затем мы можем изменить наш метод, чтобы также взять Компаратор :

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. Мы увидим, что тот же подход с сравнить с будет работать:

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. Объекты, Которые Не Реализуют Сопоставимые

В последнее время давайте снова попробуем наш объект 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 .