用Java检查数组是否已排序

1. Overview

In this tutorial, we’ll see different ways to check if an array is sorted.

Before starting, though, it’d be interesting to check how to sort arrays in Java.

2. With a Loop

One way to check is with a for loop. We can iterate all the values of the array one by one.

Let’s see how to do it.

2.1. Primitive Array

Simply put, we’ll iterate over all positions but the last one. This is because we’re going to compare one position with the next one.

If some of them are not sorted, the method will return false. If none of the comparisons return false, it means that an array is sorted:

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. Objects That Implement Comparable

We can do something similar with objects that implement Comparable. Instead of using a greater-than sign, we’ll use 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. Objects That Don’t Implement Comparable

But, what if our objects don’t implement Comparable? In this case, we can instead create a Comparator.

In this example, we’re going to use the Employee object. It’s a simple POJO with three fields:

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

    // getters and setters
}

Then, we need to choose which field we want to order by. Here, let’s order by the age field:

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

And then, we can change our method to also take a 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. Recursively

We can, of course, use recursion instead. The idea here is we’ll check two positions in the array and then recurse until we’ve checked every position.

3.1. Primitive Array

In this method, we check the last two positions. If they’re sorted, we’ll call the method again but with a previous position. If one of these positions is not sorted, the method will return 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. Objects That Implement Comparable

Now, let’s look again as objects that implement Comparable. We’ll see that the same approach with compareTo will work:

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. Objects That Don’t Implement Comparable

Lately, let’s try our Employee object again, adding the Comparator parameter:

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. Conclusion

In this tutorial, we have seen how to check if an array is sorted or not. We saw both iterative and recursive solutions.

Our recommendation is to use the loop solution. It’s cleaner and easier to read.

As usual, the source code from this tutorial can be found over on GitHub.