Sortering med Comparable och Comparator i Java

Programmerare behöver ofta sortera element från en databas i en samling, matris eller karta. I Java kan vi implementera vilken sorteringsalgoritm vi vill med vilken typ som helst. Med Comparablegränssnittet och compareTo()metoden kan vi sortera i alfabetisk ordning, Stringlängd, omvänd alfabetisk ordning eller siffror. Den ComparatorGränssnittet tillåter oss att göra samma sak, men på ett mer flexibelt sätt.

Oavsett vad vi vill göra behöver vi bara veta hur man implementerar rätt sorteringslogik för det angivna gränssnittet och typen.

Hämta källkoden

Hämta koden för denna Java Challenger. Du kan köra dina egna tester medan du följer exemplen.

Sortera en Java-lista med ett anpassat objekt

För vårt exempel använder vi samma POJO som vi hittills har använt för andra Java-utmanare. I det här första exemplet implementerar vi det jämförbara gränssnittet i Simpsonklassen med Simpsonden generiska typen:

 class Simpson implements Comparable { String name; Simpson(String name) { this.name = name; } @Override public int compareTo(Simpson simpson) { return this.name.compareTo(simpson.name); } } public class SimpsonSorting { public static void main(String... sortingWithList) { List simpsons = new ArrayList(); simpsons.add(new SimpsonCharacter("Homer ")); simpsons.add(new SimpsonCharacter("Marge ")); simpsons.add(new SimpsonCharacter("Bart ")); simpsons.add(new SimpsonCharacter("Lisa ")); Collections.sort(simpsons); simpsons.stream().map(s -> s.name).forEach(System.out::print); Collections.reverse(simpsons); simpsons.stream().forEach(System.out::print); } } 

Observera att vi har åsidosatt metoden comparTo () och skickat i ett annat Simpsonobjekt. Vi har också åsidosatt toString()metoden, bara för att göra exemplet lättare att läsa.

De toStringmetod visar all information från objektet. När vi skriver ut objektet kommer utdata att vara vad som implementerades i toString().

Metoden CompareTo ()

Den compareTo()metod jämför en givet objekt eller den aktuella förekomsten med ett angivet objekt för att bestämma ordningen av objekt. Här är en snabb titt på hur det compareTo()fungerar:

  Om jämförelsen återkommer

  Sedan ...

  >= 1

  this.name > simpson.name

  0

  this.name == simpson.name

  <= -1

  this.name < simpson.name

Vi kan bara använda klasser som är jämförbara med sort()metoden. Om vi ​​försöker skicka ett Simpsonsom inte implementeras Comparablefår vi ett kompileringsfel.

Den sort()metod använder polymorfism genom att passera alla objekt som är Comparable. Objekt sorteras sedan som förväntat.

Utgången från den föregående koden skulle vara:

 Bart Homer Lisa Marge 

Om vi ​​ville omvända ordern kunde vi byta ut sort()mot en reverse(); från:

 Collections.sort(simpsons); 

till:

 Collections.reverse(simpsons); 

Att distribuera reverse()metoden skulle ändra den tidigare utgången till:

 Marge Lisa Homer Bart 

Sortera en Java-array

I Java kan vi sortera en matris med vilken typ vi vill så länge den implementerar Comparablegränssnittet. Här är ett exempel:

 public class ArraySorting { public static void main(String... moeTavern) { int[] moesPints = new int[] {9, 8, 7, 6, 1}; Arrays.sort(moesPints); Arrays.stream(moesPints).forEach(System.out::print); Simpson[] simpsons = new Simpson[]{new Simpson("Lisa"), new Simpson("Homer")}; Arrays.sort(simpsons); Arrays.stream(simpsons).forEach(System.out::println); } } 

I den första sort()anropet sorteras matrisen till:

 1 6 7 8 9 

I den andra sort()anropet sorteras det till:

 Homer Lisa 

Tänk på att anpassade objekt måste implementeras Comparableför att kunna sorteras, även som en matris.

Kan jag sortera objekt utan jämförbara?

Om Simpson-objektet inte implementerades Comparableskulle ett ClassCastException kastas. Om du kör detta som ett test ser du ungefär följande utdata:

 Error:(16, 20) java: no suitable method found for sort(java.util.List) method java.util.Collections.sort(java.util.List) is not applicable (inference variable T has incompatible bounds equality constraints: com.javaworld.javachallengers.sortingcomparable.Simpson lower bounds: java.lang.Comparable) method java.util.Collections.sort(java.util.List,java.util.Comparator) is not applicable (cannot infer type-variable(s) T (actual and formal argument lists differ in length)) 

Den här loggen kan vara förvirrande, men oroa dig inte. Tänk bara på att en ClassCastExceptionkommer att kastas för alla sorterade objekt som inte implementerar Comparablegränssnittet.

Sortera en karta med TreeMap

Java API innehåller många klasser för att hjälpa till med sortering, inklusive TreeMap. I exemplet nedan använder vi för TreeMapatt sortera nycklar till a Map.

 public class TreeMapExample { public static void main(String... barney) { Map simpsonsCharacters = new TreeMap(); simpsonsCharacters.put(new SimpsonCharacter("Moe"), "shotgun"); simpsonsCharacters.put(new SimpsonCharacter("Lenny"), "Carl"); simpsonsCharacters.put(new SimpsonCharacter("Homer"), "television"); simpsonsCharacters.put(new SimpsonCharacter("Barney"), "beer"); System.out.println(simpsonsCharacters); } } 

TreeMapanvänder compareTo()metoden implementerad av Comparablegränssnittet. Varje element i resultatet Mapsorteras efter nyckel. I det här fallet skulle produktionen vara:

 Barney=beer, Homer=television, Lenny=Carl, Moe=shotgun 

Kom dock ihåg: om objektet inte implementeras kastas Comparableen ClassCastExceptionvilja.

Sortera en uppsättning med TreeSet

Den SetGränssnittet är ansvarig för att lagra unika värden, men när vi använder genomförande TreeSet kommer insatta element sorteras automatiskt när vi lägger till dem:

 public class TreeSetExample { public static void main(String... barney) { Set simpsonsCharacters = new TreeSet(); simpsonsCharacters.add(new SimpsonCharacter("Moe")); simpsonsCharacters.add(new SimpsonCharacter("Lenny")); simpsonsCharacters.add(new SimpsonCharacter("Homer")); simpsonsCharacters.add(new SimpsonCharacter("Barney")); System.out.println(simpsonsCharacters); } } 

Utgången från den här koden är:

 Barney, Homer, Lenny, Moe 

Återigen, om vi använder ett föremål som inte är det Comparable, ClassCastExceptionkastas en vilja.

Sortering med komparator

Vad händer om vi inte vill använda samma compareTo()metod från POJO-klassen? Kan vi åsidosätta Comparablemetoden för att använda en annan logik? Nedan följer ett exempel:

 public class BadExampleOfComparable { public static void main(String... args) { List characters = new ArrayList(); SimpsonCharacter homer = new SimpsonCharacter("Homer") { @Override public int compareTo(SimpsonCharacter simpson) { return this.name.length() - (simpson.name.length()); } }; SimpsonCharacter moe = new SimpsonCharacter("Moe") { @Override public int compareTo(SimpsonCharacter simpson) { return this.name.length() - (simpson.name.length()); } }; characters.add(homer); characters.add(moe); Collections.sort(characters); System.out.println(characters); } } 

As you can see, this code is complicated and includes a lot of repetition. We had to override the compareTo() method twice for the same logic. If there were more elements we would have to replicate the logic for each object.

Fortunately, we have the Comparator interface, which lets us detach the compareTo() logic from Java classes. Consider the same example above rewritten using Comparator:

 public class GoodExampleOfComparator { public static void main(String... args) { List characters = new ArrayList(); SimpsonCharacter homer = new SimpsonCharacter("Homer"); SimpsonCharacter moe = new SimpsonCharacter("Moe"); characters.add(homer); characters.add(moe); Collections.sort(characters, (Comparator. comparingInt(character1 -> character1.name.length()) .thenComparingInt(character2 -> character2.name.length()))); System.out.println(characters); } } 

These examples demonstrate the main difference between Comparable and Comparator.

Use Comparable when there is a single, default comparison for your object. Use Comparatorwhen you need to work around an existing compareTo(), or when you need to use specific logic in a more flexible way. Comparator detaches the sorting logic from your object and contains the compareTo() logic within your sort() method.

Using Comparator with an anonymous inner class

In this next example, we use an anonymous inner class to compare the value of objects. An anonymous inner class, in this case, is any class that implements Comparator. Using it means we are not bound to instantiating a named class implementing an interface; instead, we implement the compareTo() method inside the anonymous inner class.

 public class MarvelComparator { public static void main(String... comparator) { List marvelHeroes = new ArrayList(); marvelHeroes.add("SpiderMan "); marvelHeroes.add("Wolverine "); marvelHeroes.add("Xavier "); marvelHeroes.add("Cyclops "); Collections.sort(marvelHeroes, new Comparator() { @Override public int compare(String hero1, String hero2) { return hero1.compareTo(hero2); } }); Collections.sort(marvelHeroes, (m1, m2) -> m1.compareTo(m2)); Collections.sort(marvelHeroes, Comparator.naturalOrder()); marvelHeroes.forEach(System.out::print); } } 

More about inner classes

An anonymous inner class is simply any class whose name doesn’t matter, and which implements the interface we are declaring. So in the example, the new Comparator is actually the instantiation of a class that doesn’t have a name, which implements the method with the logic we want.

Using Comparator with lambda expressions

Anonymous inner classes are verbose, which can cause problems in our code. In the Comparator interface, we can use lambda expressions to simplify and make the code easier to read. For example, we could change this:

 Collections.sort(marvel, new Comparator() { @Override public int compare(String hero1, String hero2) { return hero1.compareTo(hero2); } }); 

to this:

 Collections.sort(marvel, (m1, m2) -> m1.compareTo(m2)); 

Less code and the same result!

The output of this code would be:

 Cyclops SpiderMan Wolverine Xavier 

We could make the code even simpler by changing this:

 Collections.sort(marvel, (m1, m2) -> m1.compareTo(m2)); 

to this:

 Collections.sort(marvel, Comparator.naturalOrder()); 

Lambda expressions in Java

Learn more about lambda expressions and other functional programming techniques in Java.

Are the core Java classes Comparable?

Many core Java classes and objects implement the Comparable interface, which means we don’t have to implement the compareTo() logic for those classes. Here are a few familiar examples:

String

 public final class String implements java.io.Serializable, Comparable, CharSequence { ... 

Integer

 public final class Integer extends Number implements Comparable { … 

Double

 public final class Double extends Number implements Comparable {... 

There are many others. I encourage you to explore the Java core classes to learn their important patterns and concepts.

Ta den jämförbara gränssnittsutmaningen!

Testa vad du har lärt dig genom att räkna ut resultatet av följande kod. Kom ihåg att du lär dig bäst om du löser den här utmaningen själv genom att bara studera den. När du har nått ett svar kan du kontrollera svaret nedan. Du kan också köra dina egna tester för att helt absorbera koncepten.

 public class SortComparableChallenge { public static void main(String... doYourBest) { Set set = new TreeSet(); set.add(new Simpson("Homer")); set.add(new Simpson("Marge")); set.add(new Simpson("Lisa")); set.add(new Simpson("Bart")); set.add(new Simpson("Maggie")); List list = new ArrayList(); list.addAll(set); Collections.reverse(list); list.forEach(System.out::println); } static class Simpson implements Comparable { String name; public Simpson(String name) { this.name = name; } public int compareTo(Simpson simpson) { return simpson.name.compareTo(this.name); } public String toString() { return this.name; } } } 

Vilken är utgången från den här koden?

 A) Bart Homer Lisa Maggie Marge B) Maggie Bart Lisa Marge Homer C) Marge Maggie Lisa Homer Bart D) Indeterminate