Сортировка - одна из распротсраненных задач при работе с данными. В Java в различных структурах данных есть встроенная поддержка сортировки. Однако для поддержки сортировки обычно требуется реализация двух интерфейсов: Comparable и Comparator
Многие встроенные коллекции в Java имеют методы сортировки, которые обычно называются sort(). Например, в интерфейсе List, который определяет базовый функционал для коллекций-списков,
есть подобный метод:
default void sort(Comparator<? super E> c)
То есть, чтобы отсортировать список, нам надо в метод sort() передать компаратор - объект типа Comparator, который типизирован типом элементов списка.
Компаратор позволяет сравнить два объекта.
Интерфейс Comparator содержит ряд методов, ключевым из которых является метод compare():
public interface Comparator<T> {
int compare(T a, T b);
// остальные методы
}
Метод compare принимает два сравниваемых объекта и возвращает числовое значение в зависимости от результата сравнения:
Если объект a предшествует объекту b (грубо говоря, a < b), то возвращается отрицательное значение
Если объект a идет после объекта b (a > b), то возвращается положительное значение
Если объекты равны (a == b), то возвращается ноль
Для применения интерфейса необходимо создать класс компаратора, который реализует этот интерфейс. Например, у нас есть следующий класс Person:
class Person{
private String name;
private int age;
String getName(){ return name; }
int getAge(){ return age;}
Person(String name, int age){
this.name = name;
this.age = age;
}
void print(){
System.out.printf("Person Name: %s; Age: %d;\n", name, age);
}
}
Допустим, мы хотим сравнивать два объекта Person, благодаря чему будет производиться сортировка. Для этого определим следующий класс компаратора:
class PersonNameComparator implements Comparator<Person>{
public int compare(Person a, Person b){
return a.getName().compareTo(b.getName());
}
}
Здесь в реализации мы сравниваем по полю name. Для этого используем метод compareTo(), который есть у строк и который позволяет сравнить две строки. Это удобно, поскольку нам не надо дополнительно определять логику сравнения символов строк, а можно воспользоваться готовым функционалом. То есть, если a.name условно меньше (в лексекографическом поряке размещается ранее), чем
b.name, то метод compareTo() возвращает отрицательное число. Если a.name условно больше, чем b.name, то возвращается положительное число. Если строки равны, то возвращается 0.
Хотя в реальности мы могли бы определить и свою логику, например, сравнивать по длине имени:
class PersonNameComparator implements Comparator<Person>{
public int compare(Person a, Person b){
return a.getName().length()-p.getName().length();
}
}
Посмотрим, как все это используется:
import java.util.ArrayList;
import java.util.Comparator;
public class Program{
public static void main(String[] args) {
var people = new ArrayList<Person>();
people.add(new Person("Tom", 41));
people.add(new Person("Bob", 46));
people.add(new Person("Sam", 28));
people.sort(new PersonNameComparator());
for(var p : people){
p.print();
}
}
}
class PersonNameComparator implements Comparator<Person>{
public int compare(Person a, Person b){
return a.getName().compareTo(b.getName());
}
}
class Person{
private String name;
private int age;
String getName(){ return name; }
int getAge(){ return age;}
Person(String name, int age){
this.name = name;
this.age = age;
}
void print(){
System.out.printf("Person Name: %s; Age: %d;\n", name, age);
}
}
Здесь мы определяем список объектов Person и используем компаратор PersonNameComparator для сортировки списка:
people.sort(new PersonComparator());
Благодаря этому при выводе на консоль мы увидим список, отсортированный в зависимости от поля name:
Person Name: Bob; Age: 46; Person Name: Sam; Age: 28; Person Name: Tom; Age: 41;
Аналогично мы могли бы определить компаратор для сравнения по полю age:
import java.util.ArrayList;
import java.util.Comparator;
public class Program{
public static void main(String[] args) {
var people = new ArrayList<Person>();
people.add(new Person("Tom", 41));
people.add(new Person("Bob", 46));
people.add(new Person("Sam", 28));
people.sort(new PersonAgeComparator());
for(var p : people){
p.print();
}
}
}
class PersonAgeComparator implements Comparator<Person>{
public int compare(Person a, Person b){
return a.getAge() - b.getAge();
}
}
class Person{
private String name;
private int age;
String getName(){ return name; }
int getAge(){ return age;}
Person(String name, int age){
this.name = name;
this.age = age;
}
void print(){
System.out.printf("Person Name: %s; Age: %d;\n", name, age);
}
}
Здесь в качестве компаратора применяется класс PersonAgeComparator, логика которого тоже не отличается сложностью: просто возващаем результат выражения a.getAge() - b.getAge().
Что фактически эквивалентно, если бы мы расписали это следующим образом:
class PersonAgeComparator implements Comparator<Person>{
public int compare(Person a, Person b){
if(a.getAge() > b.getAge())
return 1;
else if(a.getAge() < b.getAge())
return -1;
else
return 0;
}
}
Но операция вычитания a.getAge() - b.getAge() гораздо проще и производительнее, чем условная конструкция.
В итоге теперь мы получим другой вывод - с сортировкой по полю age:
Person Name: Sam; Age: 28; Person Name: Tom; Age: 41; Person Name: Bob; Age: 46;
Также мы можем применять сразу несколько компараторов по принципу приоритета. Например, мы хотим, чтобы сначала сортировка шла по полю name, а если есть несколько объектов с одинаковым полем name, то применять сортировку по полю age.
Интерфейс компаратора определяет специальный метод thenComparing(), который позволяет использовать цепочки компараторов для сортировки набора::
import java.util.ArrayList;
import java.util.Comparator;
public class Program{
public static void main(String[] args) {
var people = new ArrayList<Person>();
people.add(new Person("Tom", 22));
people.add(new Person("Tom", 41));
people.add(new Person("Bob", 46));
people.add(new Person("Bob", 37));
people.add(new Person("Sam", 28));
Comparator<Person> totalComparator = new PersonNameComparator().thenComparing(new PersonAgeComparator());
people.sort(totalComparator);
for(var p : people){
p.print();
}
}
}
В данном случае с помощью вызовов
PersonNameComparator().thenComparing(new PersonAgeComparator());
создаем цепочку компараторов в виде условно общего компаратора totalComparator, который затем используется для сортировки. В итоге теперь мы получим следующий консольный вывод:
Person Name: Bob; Age: 37; Person Name: Bob; Age: 46; Person Name: Sam; Age: 28; Person Name: Tom; Age: 22; Person Name: Tom; Age: 41;
Кроме интерфейса Comparator для сравнения объектов применяется другой интерфейс - Comparable. Данный интерфейс довольно прост, определяя один метод compareTo():
public interface Comparable
{
int compareTo(Object other);
}
Этот метод служит тем же целям, что и метод compare в интерфейсе Comparator. Метод compareTo() принимает объект, сравнивает его с текущим и возвращает числовое
значение в зависимости от результата сравнения:
Если текущий объект меньше объекта other, то возвращается отрицательное значение
Если текущий объект больше объекта other, то возвращается положительное значение
Если объекты равны, то возвращается ноль
Некоторые встроенные классы в JDK уже по умолчанию реализуют этот интерфейс. Так, выше в примере с компаратором PersonNameComparator для сравнения строк мы использовали метод compareTo()
return a.getName().compareTo(b.getName());
То есть в данном случае мы как раз и использовали реализацию интерфейса Comparable в строках. И мы можем использовать ее при сортировке объектов, например, в том же списке:
import java.util.ArrayList;
public class Program{
public static void main(String[] args) {
var people = new ArrayList<String>();
people.add("Tom");
people.add("Bob");
people.add("Sam");
people.sort(null);
for(var p : people){
System.out.println(p);
}
}
}
Здесь мы определяем и сортируем список строк. Консольный вывод:
Bob Sam Tom
Почему здесь выполняется сортировка? Если в метод sort() для компаратора передается значение null, то для выполнения сортировки все элементы в этом списке должны
реализовывать интерфейс Comparable. И эта реализация и будет применяться для сортировки. То есть в случае выше для сортировки строк неявно применяется реализация интерфейса Comparable.
И мы также можем реализовать данный интерфейс и в своих кастомных классах:
class Person implements Comparable<Person>{
private String name;
private int age;
String getName(){ return name; }
int getAge(){ return age;}
Person(String name, int age){
this.name = name;
this.age = age;
}
void print(){
System.out.printf("Person Name: %s; Age: %d;\n", name, age);
}
public int compareTo(Person p){
return name.compareTo(p.getName());
}
}
В данном случае мы не возвращаем явным образом никакое число, а опять же полагаемся на встроенный механизм сравнения, который есть у класса String.
Применение в программе:
import java.util.ArrayList;
public class Program{
public static void main(String[] args) {
var people = new ArrayList<Person>();
people.add(new Person("Tom", 41));
people.add(new Person("Bob", 46));
people.add(new Person("Sam", 28));
people.sort(null); // сортировка на основе реализации Comparable
for(var p : people){
p.print();
}
}
}
class Person implements Comparable<Person>{
private String name;
private int age;
String getName(){ return name; }
int getAge(){ return age;}
Person(String name, int age){
this.name = name;
this.age = age;
}
void print(){
System.out.printf("Person Name: %s; Age: %d;\n", name, age);
}
public int compareTo(Person p){
return name.compareTo(p.getName());
}
}
Консольный вывод программы:
Person Name: Bob; Age: 46; Person Name: Sam; Age: 28; Person Name: Tom; Age: 41;