Sorteren in Java

1. Overzicht

Dit artikel illustreert hoe u sortering kunt toepassen op Array, Lijst, Set en Kaart in Java 7 en Java 8.

2. Sorteren met Array

Laten we beginnen met het sorteren van integer-arrays eerst met Arrays.sort () methode.

We zullen het volgende definiëren int arrays in een @Voordat jUnit-methode:

@Before public void initVariables () {toSort = new int [] {5, 1, 89, 255, 7, 88, 200, 123, 66}; sortInts = new int [] {1, 5, 7, 66, 88, 89, 123, 200, 255}; gesorteerdRangeInts = nieuwe int [] {5, 1, 89, 7, 88, 200, 255, 123, 66}; ...}

2.1. Volledige reeks sorteren

Laten we nu het simpele gebruiken Array.sort () API:

@Test openbare leegte gegevenIntArray_whenUsingSort_thenSortedArray () {Arrays.sort (toSort); assertTrue (Arrays.equals (toSort, sortInts)); }

De ongesorteerde array is nu volledig gesorteerd:

[1, 5, 7, 66, 88, 89, 123, 200, 255]

Zoals vermeld in de officiële JavaDoc, Arrays.sort gebruikt dual-pivot Quicksort aan primitieven. Het biedt O (n log (n)) prestaties en is doorgaans sneller dan traditionele (één draaipunt) Quicksort-implementaties. Het gebruikt echter een stabiele, adaptieve, iteratieve implementatie van het mergesort-algoritme voor Array van objecten.

2.2. Een deel van een array sorteren

Arrays.sort heeft er nog een soort API's - die we hier zullen bespreken:

Arrays.sort (int [] a, int fromIndex, int toIndex)

Hierdoor wordt slechts een deel van de array tussen de twee indices gesorteerd.

Laten we een snel voorbeeld bekijken:

@Test openbare leegte gegevenIntArray_whenUsingRangeSort_thenRangeSortedArray () {Arrays.sort (toSort, 3, 7); assertTrue (Arrays.equals (toSort, sortRangeInts)); }

Het sorteren wordt alleen gedaan op de volgende subarray-elementen (indexeren zou exclusief zijn):

[255, 7, 88, 200]

De resulterende gesorteerde subarray inclusief de hoofdarray zou zijn:

[5, 1, 89, 7, 88, 200, 255, 123, 66]

2.3. Java 8 Arrays.sort vs Arrays.parallelSort

Java 8 wordt geleverd met een nieuwe API - parallelSort - met een soortgelijke handtekening als de Arrays.sort () API:

@Test openbare leegte gegevenIntArray_whenUsingParallelSort_thenArraySorted () {Arrays.parallelSort (toSort); assertTrue (Arrays.equals (toSort, sortInts)); }

Achter de schermen van parallelSort (), het verdeelt de array in verschillende sub-arrays (volgens granulariteit in het algoritme van parallelSort). Elke sub-array wordt gesorteerd met Arrays.sort () in verschillende draden zodat soort kunnen parallel worden uitgevoerd en worden uiteindelijk samengevoegd als een gesorteerde array.

Merk op dat de gemeenschappelijke ForJoin-pool wordt gebruikt voor het uitvoeren van deze parallelle taken en het vervolgens samenvoegen van de resultaten.

Het resultaat van de Arrays.parallelSort zal hetzelfde zijn als Array. Sorteren het is natuurlijk gewoon een kwestie van multi-threading gebruiken.

Ten slotte zijn er vergelijkbare varianten van API Arrays.sort in Arrays.parallelSort ook:

Arrays.parallelSort (int [] a, int fromIndex, int toIndex);

3. Sorteren van een Lijst

Laten we nu de Collections.sort () API in java.utils.Collections - om een Lijst van gehele getallen:

@Test openbare ongeldig gegevenList_whenUsingSort_thenSortedList () {List toSortList = Ints.asList (toSort); Collections.sort (toSortList); assertTrue (Arrays.equals (toSortList.toArray (), ArrayUtils.toObject (sortInts))); }

De Lijst voordat het sorteren de volgende elementen bevat:

[5, 1, 89, 255, 7, 88, 200, 123, 66]

En natuurlijk na het sorteren:

[1, 5, 7, 66, 88, 89, 123, 200, 255]

Zoals vermeld in Oracle JavaDoc voor Collecties.Sort, het maakt gebruik van een aangepaste samenvoeging en aanbiedingen gegarandeerd n logboek (n) prestatie.

4. Sorteren van een Set

Laten we vervolgens gebruiken Collections.sort () om een LinkedHashSet.

We gebruiken de LinkedHashSet omdat het de invoegvolgorde handhaaft.

Merk op hoe u de soort API in Collectieswe wikkelen de set eerst in een lijst:

@Test openbare ongeldige gegevenSet_whenUsingSort_thenSortedSet () {Set integersSet = nieuwe LinkedHashSet (Ints.asList (toSort)); Set descSortedIntegersSet = new LinkedHashSet (Arrays.asList (new Integer [] {255, 200, 123, 89, 88, 66, 7, 5, 1})); Lijstlijst = nieuwe ArrayList (integersSet); Collections.sort (Comparator.reverseOrder ()); integersSet = nieuwe LinkedHashSet (lijst); assertTrue (Arrays.equals (integersSet.toArray (), descSortedIntegersSet.toArray ())); }

De Comparator.reverseOrder () methode keert de ordening om die wordt opgelegd door de natuurlijke ordening.

5. Sorteren Kaart

In dit gedeelte gaan we kijken naar een kaart sorteren - zowel op sleutels als op waarden.

Laten we eerst de kaart definiëren die we gaan sorteren:

@Before public void initVariables () {.... HashMap map = nieuwe HashMap (); map.put (55, "John"); map.put (22, "Apple"); map.put (66, "Earl"); map.put (77, "Pearl"); map.put (12, "George"); map.put (6, "Rocky"); ....}

5.1. Sorteren Kaart door Keys

We zullen het nu uitpakken sleutels en waarden inzendingen uit de Hash kaart en sorteer het op basis van de waarden van de sleutels in dit voorbeeld:

@Test openbare ongeldige gegevenMap_whenSortingByKeys_thenSortedMap () {Geheel getal [] gesorteerdKeys = nieuw geheel getal [] {6, 12, 22, 55, 66, 77}; Lijst inzendingen = nieuwe ArrayList (map.entrySet ()); Collections.sort (inzendingen, nieuwe Comparator() {@Override public int Compare (Entry o1, Entry o2) {return o1.getKey (). CompareTo (o2.getKey ()); }}); Map gesorteerdMap = nieuwe LinkedHashMap (); voor (Map.Entry entry: entries) {gesorteerdMap.put (entry.getKey (), entry.getValue ()); } assertTrue (Arrays.equals (gesorteerdMap.keySet (). toArray (), gesorteerdKeys)); }

Merk op hoe we het LinkedHashMap tijdens het kopiëren van de gesorteerde Inzendingen gebaseerd op sleutels (omdat HashSet garandeert niet de volgorde van de sleutels).

De Kaart voor het sorteren:

[Sleutel: 66, Waarde: Earl] [Sleutel: 22, Waarde: Apple] [Sleutel: 6, Waarde: Rocky] [Sleutel: 55, Waarde: John] [Sleutel: 12, Waarde: George] [Sleutel: 77, Waarde: Pearl]

De Kaart na het sorteren met sleutels:

[Sleutel: 6, Waarde: Rocky] [Sleutel: 12, Waarde: George] [Sleutel: 22, Waarde: Apple] [Sleutel: 55, Waarde: John] [Sleutel: 66, Waarde: Earl] [Sleutel: 77, Waarde: Pearl] 

5.2. Sorteren Kaart op waarden

Hier zullen we waarden van vergelijken Hash kaart items om te sorteren op basis van waarden van Hash kaart:

@Test openbare ongeldige gegevenMap_whenSortingByValues_thenSortedMap () {String [] gesorteerdeValues ​​= nieuwe String [] {"Apple", "Earl", "George", "John", "Pearl", "Rocky"}; Lijst inzendingen = nieuwe ArrayList (map.entrySet ()); Collections.sort (inzendingen, nieuwe Comparator() {@Override public int Compare (Entry o1, Entry o2) {return o1.getValue (). CompareTo (o2.getValue ()); }}); Map gesorteerdMap = nieuwe LinkedHashMap (); voor (Map.Entry entry: entries) {gesorteerdMap.put (entry.getKey (), entry.getValue ()); } assertTrue (Arrays.equals (gesorteerdeMap.values ​​(). toArray (), gesorteerdeValues)); }

De Kaart voor het sorteren:

[Sleutel: 66, Waarde: Earl] [Sleutel: 22, Waarde: Apple] [Sleutel: 6, Waarde: Rocky] [Sleutel: 55, Waarde: John] [Sleutel: 12, Waarde: George] [Sleutel: 77, Waarde: Pearl]

De Kaart na het sorteren door waarden:

[Key: 22, Value: Apple] [Key: 66, Value: Earl] [Key: 12, Value: George] [Key: 55, Value: John] [Key: 77, Value: Pearl] [Key: 6, Waarde: Rocky]

6. Aangepaste objecten sorteren

Laten we nu werken met een aangepast object:

openbare klasse Werknemer implementeert vergelijkbare {private String-naam; privé int leeftijd; particulier dubbel salaris; openbare werknemer (String naam, int leeftijd, dubbel salaris) {...} // standaard getters, setters en toString}

We zullen het volgende gebruiken Werknemer Matrix voor sorteervoorbeeld in de volgende secties:

@Before public void initVariables () {.... werknemers = nieuwe werknemer [] {nieuwe werknemer ("John", 23, 5000), nieuwe werknemer ("Steve", 26, 6000), nieuwe werknemer ("Frank", 33, 7000), nieuwe werknemer ("Earl", 43, 10000), nieuwe werknemer ("Jessica", 23, 4000), nieuwe werknemer ("Pearl", 33, 6000)}; workersSorted = nieuwe werknemer [] {nieuwe werknemer ("Earl", 43, 10000), nieuwe werknemer ("Frank", 33, 70000), nieuwe werknemer ("Jessica", 23, 4000), nieuwe werknemer ("John", 23, 5000), nieuwe werknemer ("Pearl", 33, 4000), nieuwe werknemer ("Steve", 26, 6000)}; werknemersSortedByAge = nieuwe werknemer [] {nieuwe werknemer ("John", 23, 5000), nieuwe werknemer ("Jessica", 23, 4000), nieuwe werknemer ("Steve", 26, 6000), nieuwe werknemer ("Frank", 33, 70000), nieuwe werknemer ("Pearl", 33, 4000), nieuwe werknemer ("Earl", 43, 10000)}; }

We kunnen arrays of verzamelingen aangepaste objecten sorteren:

  1. in de natuurlijke volgorde (met behulp van de Vergelijkbaar Interface) of
  2. in de volgorde van a ComparatorKoppel

6.1. Uzing Vergelijkbaar

De natuurlijke volgorde in Java betekent een volgorde waarin primitief of Object geordend moet worden gesorteerd in een gegeven array of verzameling.

Beide java.util.Arrays en java.util.Collections heb een soort() methode, en Het wordt ten zeerste aanbevolen dat natuurlijke ordes consistent moeten zijn met de semantiek van is gelijk aan.

In dit voorbeeld zullen we werknemers met hetzelfde beschouwen naam als gelijk:

@Test openbare leegte gegevenEmpArray_SortEmpArray_thenSortedArrayinNaturalOrder () {Arrays.sort (werknemers); assertTrue (Arrays.equals (werknemers, werknemers gesorteerd)); }

U kunt de natuurlijke volgorde voor elementen definiëren door een Vergelijkbaar interface die heeft vergelijk met() methode voor het vergelijken van het huidige object en het object dat als argument is doorgegeven.

Laten we een voorbeeld bekijken om dit duidelijk te begrijpen Werknemer klasse die implementeert Vergelijkbaar Koppel:

public class Medewerker implementeert Vergelijkbaar {... @Override public boolean equals (Object obj) {return ((Employee) obj) .getName (). equals (getName ()); } @Override public int CompareTo (Object o) {Employee e = (Employee) o; retourneer getName (). CompareTo (e.getName ()); }}

Over het algemeen zal de logica voor vergelijking de methode worden geschreven vergelijk met. Hier vergelijken we de werknemersorder of naam van het werknemersveld. Twee medewerkers zijn gelijk als ze dezelfde naam hebben.

Nu wanneer Arrays.sort (medewerkers); wordt genoemd in de bovenstaande code, we weten nu wat de logica en volgorde is bij het sorteren van de werknemers op basis van de leeftijd:

[("Earl", 43, 10000), ("Frank", 33, 70000), ("Jessica", 23, 4000), ("John", 23, 5000), ("Pearl", 33, 4000) , ("Steve", 26, 6000)]

We kunnen zien dat de array is gesorteerd op naam van de medewerker - wat nu een natuurlijke volgorde wordt voor Werknemer Klasse.

6.2. Gebruik makend van Comparator

Laten we nu de elementen sorteren met behulp van een Comparator interface-implementatie - waar we de anonieme inner class on-the-fly doorgeven aan de Arrays.sort () API:

@Test openbare leegte gegevenIntegerArray_whenUsingSort_thenSortedArray () {Geheel getal [] gehele getallen = ArrayUtils.toObject (toSort); Arrays.sort (integers, new Comparator () {@Override public int Compare (Integer a, Integer b) {return Integer.compare (a, b);}}); assertTrue (Arrays.equals (gehele getallen, ArrayUtils.toObject (sortInts))); }

Laten we nu werknemers sorteren op basis van salaris - en slagen voor een andere comparator-implementatie:

Arrays.sort (werknemers, nieuwe Comparator () {@Override openbare int vergelijken (werknemer o1, werknemer o2) {return Double.compare (o1.getSalary (), o2.getSalary ());}});

De gesorteerde Werknemers-arrays zijn gebaseerd op salaris zal zijn:

[(Jessica, 23,4000,0), (John, 23,5000,0), (Pearl, 33,6000,0), (Steve, 26,6000,0), (Frank, 33,7000,0), (Earl, 43,10000,0)] 

Merk op dat we kunnen gebruiken Collections.sort () op een vergelijkbare manier te sorteren Lijst en Set van objecten in natuurlijke of aangepaste volgorde, zoals hierboven beschreven voor arrays.

7. Sorteren met Lambda's

Begin met Java 8, we kunnen Lambdas gebruiken om het Comparator Functionele interface.

U kunt de Lambdas in Java 8-beschrijving bekijken om de syntaxis op te frissen.

Laten we de oude comparator vervangen:

Comparator c = nieuwe Comparator () {@Override public int Compare (Integer a, Integer b) {return Integer.compare (a, b); }}

Met de equivalente implementatie, met behulp van Lambda-expressie:

Comparator c = (a, b) -> Geheel getal. Vergelijk (a, b);

Laten we tot slot de test schrijven:

@Test openbare leegte gegevenArray_whenUsingSortWithLambdas_thenSortedArray () {Geheel getal [] gehele getallenToSort = ArrayUtils.toObject (toSort); Arrays.sort (integersToSort, (a, b) -> {return Integer.compare (a, b);}); assertTrue (Arrays.equals (integersToSort, ArrayUtils.toObject (sortInts))); }

Zoals u kunt zien, een veel schonere en beknoptere logica hier.

8. Met behulp van Comparator.comparing en Comparator.thenComparing

Java 8 wordt geleverd met twee nieuwe API's die handig zijn om te sorteren - vergelijken () en thenComparing () in de Comparator koppel.

Deze zijn erg handig voor het koppelen van meerdere voorwaarden van de Comparator.

Laten we eens kijken naar een scenario waarin we misschien willen vergelijken Werknemer door leeftijd en dan door naam:

@Test openbare leegte gegevenArrayObjects_whenUsingComparing_thenSortedArrayObjects () {List workersList = Arrays.asList (werknemers); workers.sort (Comparator.comparing (Employee :: getAge)); assertTrue (Arrays.toString (workers.toArray ()) .equals (gesorteerdArrayString)); }

In dit voorbeeld Werknemer :: getAge is de sorteersleutel voor Comparator interface die een functionele interface met vergelijkingsfunctie implementeert.

Hier is de reeks werknemers na het sorteren:

[(John, 23,5000,0), (Jessica, 23,4000,0), (Steve, 26,6000,0), (Frank, 33,7000,0), (Pearl, 33,6000,0), (Earl, 43,10000,0)]

Hier worden de medewerkers gesorteerd op basis van leeftijd.

We kunnen zien John en Jessica zijn van dezelfde leeftijd - wat betekent dat de ordeningslogica nu rekening moet houden met hun namen - waarmee we kunnen bereiken thenComparing ():

... workers.sort (Comparator.comparing (Employee :: getAge) .thenComparing (Employee :: getName)); ... 

Na het sorteren met het bovenstaande codefragment, worden de elementen in de werknemersarray gesorteerd als:

[(Jessica, 23,4000,0), (John, 23,5000,0), (Steve, 26,6000,0), (Frank, 33,7000,0), (Pearl, 33,6000,0), (Earl, 43,10000,0)]

Dus vergelijken () en thenComparing () maak zeker meer complexe sorteerscenario's een stuk schoner om te implementeren.

9. Conclusie

In dit artikel hebben we gezien hoe we sortering kunnen toepassen op Array, Lijst, Set, en Kaart.

We zagen ook een korte introductie over hoe functies van Java 8 nuttig kunnen zijn bij het sorteren, zoals het gebruik van Lambdas, vergelijken () en thenComparing () en parallelSort ().

Alle voorbeelden die in het artikel worden gebruikt, zijn beschikbaar op GitHub.


$config[zx-auto] not found$config[zx-overlay] not found