streamalism.org

1. Oversigt

Denne artikel vil illustrere, hvordan man anvender sortering på Array, Liste, Sæt og Kort i Java 7 og Java 8.

2. Sortering med Array

Lad os starte med at sortere heltal arrays først ved hjælp af Arrays.sort () metode.

Vi definerer følgende int arrays i en @Før jUnit-metode:

@Før offentlige ugyldige initVariables () {toSort = new int [] {5, 1, 89, 255, 7, 88, 200, 123, 66}; sortedInts = new int [] {1, 5, 7, 66, 88, 89, 123, 200, 255}; sortedRangeInts = new int [] {5, 1, 89, 7, 88, 200, 255, 123, 66}; ...}

2.1. Sortering komplet matrix

Lad os nu bruge det enkle Array.sort () API:

@Test offentlig ugyldighed givenIntArray_whenUsingSort_thenSortedArray () {Arrays.sort (toSort); assertTrue (Arrays.equals (toSort, sortedInts)); }

Det usorterede array er nu fuldt sorteret:

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

Som nævnt i den officielle JavaDoc, Arrays.sort bruger dual-pivot Quicksort til primitiver. Det tilbyder O (n log (n)) ydeevne og er typisk hurtigere end traditionelle (en-pivot) Quicksort-implementeringer. Imidlertid bruger den en stabil, adaptiv, iterativ implementering af mergesort-algoritme til Array af objekter.

2.2. Sortering af en del af en matrix

Arrays.sort har en mere sortere API'er - som vi diskuterer her:

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

Dette vil kun sortere en del af arrayet mellem de to indekser.

Lad os se på et hurtigt eksempel:

@Test offentligt ugyldigt givenIntArray_whenUsingRangeSort_thenRangeSortedArray () {Arrays.sort (toSort, 3, 7); assertTrue (Arrays.equals (toSort, sortedRangeInts)); }

Sorteringen udføres kun på følgende underarrayelementer (toIndex ville være eksklusiv):

[255, 7, 88, 200]

Den resulterende sorterede undergruppe inklusive hovedarrayet ville være:

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

2.3. Java 8 Arrays.sort vs. Arrays.parallelSort

Java 8 leveres med en ny API - parallelSort - med en lignende underskrift som Arrays.sort () API:

@Test offentlig ugyldighed givenIntArray_whenUsingParallelSort_thenArraySorted () {Arrays.parallelSort (toSort); assertTrue (Arrays.equals (toSort, sortedInts)); }

Bag kulisserne i parallelSort (), det opdeler arrayet i forskellige underarrays (som pr granularitet i algoritmen for parallelSort). Hver undergruppe er sorteret efter Arrays.sort () i forskellige tråde, så at sortere kan udføres parallelt og flettes endelig som et sorteret array.

Bemærk, at ForJoin-fællespuljen bruges til at udføre disse parallelle opgaver og derefter flette resultaterne.

Resultatet af Arrays.parallelSort bliver det samme som Array.sort selvfølgelig er det bare et spørgsmål om at udnytte multi-threading.

Endelig er der lignende varianter af API Arrays.sort i Arrays.parallelSort såvel:

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

3. Sortering a Liste

Lad os nu bruge Collections.sort () API i java.utils.Collections - at sortere en Liste af heltal:

@Test public void givenList_whenUsingSort_thenSortedList () {List toSortList = Ints.asList (toSort); Collections.sort (toSortList); assertTrue (Arrays.equals (toSortList.toArray (), ArrayUtils.toObject (sortedInts))); }

Det Liste inden sortering vil indeholde følgende elementer:

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

Og naturligvis efter sortering:

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

Som nævnt i Oracle JavaDoc for Samlinger. Sort, det bruger en modificeret fusionssort og tilbyder garanteret n log (n) ydeevne.

4. Sortering a Sæt

Lad os derefter bruge Collections.sort () at sortere en LinkedHashSet.

Vi bruger LinkedHashSet fordi det opretholder indsætningsrækkefølgen.

Bemærk hvordan, for at bruge sortere API i Samlinger – vi indpakker først sættet på en liste:

@ Test offentligt ugyldigt givenSet_whenUsingSort_thenSortedSet () {Set integersSet = new LinkedHashSet (Ints.asList (toSort)); Indstil descSortedIntegersSet = ny LinkedHashSet (Arrays.asList (nyt heltal [] {255, 200, 123, 89, 88, 66, 7, 5, 1})); List list = new ArrayList (integersSet); Collections.sort (Comparator.reverseOrder ()); integersSet = ny LinkedHashSet (liste); assertTrue (Arrays.equals (integersSet.toArray (), descSortedIntegersSet.toArray ())); }

Det Comparator.reverseOrder () metoden vender ordren pålagt af den naturlige ordning.

5. Sortering Kort

I dette afsnit begynder vi at se på sortering af et kort - både efter taster og værdier.

Lad os først definere det kort, vi skal sortere:

@Før offentlige ugyldige initVariables () {.... HashMap-kort = nyt 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. Sortering Kort af Keys

Vi udtrækker nu nøgler og værdier poster fra HashMap og sorter det ud fra værdierne på tasterne i dette eksempel:

@Test offentligt ugyldigt givenMap_whenSortingByKeys_thenSortedMap () {Integer [] sortedKeys = new Integer [] {6, 12, 22, 55, 66, 77}; Liste poster = ny ArrayList (map.entrySet ()); Collections.sort (poster, ny komparator() {@Override public int compare (Entry o1, Entry o2) {return o1.getKey (). ComparTo (o2.getKey ()); }}); Map sortedMap = new LinkedHashMap (); for (Map.Entry entry: entries) {sortedMap.put (entry.getKey (), entry.getValue ()); } assertTrue (Arrays.equals (sortedMap.keySet (). toArray (), sortedKeys)); }

Bemærk hvordan vi brugte LinkedHashMap mens du kopierer det sorterede Indlæg baseret på nøgler (fordi HashSet garanterer ikke rækkefølgen af ​​nøgler).

Det Kort inden sortering:

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

Det Kort efter sortering med tasterne:

[Nøgle: 6, Værdi: Rocky] [Nøgle: 12, Værdi: George] [Nøgle: 22, Værdi: Apple] [Nøgle: 55, Værdi: John] [Nøgle: 66, Værdi: Earl] [Nøgle: 77, Værdi: Pearl] 

5.2. Sortering Kort af værdier

Her sammenligner vi værdier af HashMap poster til sortering baseret på værdier af HashMap:

@Test offentligt ugyldigt givenMap_whenSortingByValues_thenSortedMap () {String [] sortedValues ​​= new String [] {"Apple", "Earl", "George", "John", "Pearl", "Rocky"}; Liste poster = ny ArrayList (map.entrySet ()); Collections.sort (poster, ny komparator() {@Override public int compare (Entry o1, Entry o2) {return o1.getValue (). ComparTo (o2.getValue ()); }}); Map sortedMap = new LinkedHashMap (); for (Map.Entry entry: entries) {sortedMap.put (entry.getKey (), entry.getValue ()); } assertTrue (Arrays.equals (sortedMap.values ​​(). toArray (), sortedValues)); }

Det Kort inden sortering:

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

Det Kort efter sortering efter værdier:

[Nøgle: 22, Værdi: Apple] [Nøgle: 66, Værdi: Earl] [Nøgle: 12, Værdi: George] [Nøgle: 55, Værdi: John] [Nøgle: 77, Værdi: Pearl] [Nøgle: 6, Værdi: Stenet]

6. Sortering af brugerdefinerede objekter

Lad os nu arbejde med et brugerdefineret objekt:

offentlig klasse Medarbejderværktøjer Sammenlignelig {privat strengnavn; privat int alder privat dobbelt løn offentlig ansat (strengnavn, alder, dobbelt løn) {...} // standard getters, setters og toString}

Vi bruger følgende Medarbejder Array til sorteringseksempel i de følgende sektioner:

@Før offentlige ugyldige initVariables () {.... medarbejdere = ny medarbejder [] {ny medarbejder ("John", 23, 5000), ny medarbejder ("Steve", 26, 6000), ny medarbejder ("Frank", 33, 7000), ny medarbejder ("Earl", 43, 10000), ny medarbejder ("Jessica", 23, 4000), ny medarbejder ("Pearl", 33, 6000)}; workersSorted = ny medarbejder [] {ny medarbejder ("Earl", 43, 10000), ny medarbejder ("Frank", 33, 70000), ny medarbejder ("Jessica", 23, 4000), ny medarbejder ("John", 23, 5000), ny medarbejder ("Pearl", 33, 4000), ny medarbejder ("Steve", 26, 6000)}; workersSortedByAge = ny medarbejder [] {ny medarbejder ("John", 23, 5000), ny medarbejder ("Jessica", 23, 4000), ny medarbejder ("Steve", 26, 6000), ny medarbejder ("Frank", 33, 70000), ny medarbejder ("Pearl", 33, 4000), ny medarbejder ("Earl", 43, 10000)}; }

Vi kan sortere arrays eller samlinger af brugerdefinerede objekter enten:

1. i den naturlige rækkefølge (Brug af Sammenlignelig Interface) eller
2. i den rækkefølge, der leveres af a KomparatorInterface

6.1. Usyng Sammenlignelig

Den naturlige rækkefølge i java betyder en rækkefølge, hvor primitiv eller objekt skal sorteres ordentligt i en given matrix eller samling.

Begge java.util.Arrays og java.util.Collections have en sortere() metode og Det anbefales stærkt, at naturlige ordrer skal være i overensstemmelse med semantikken i lige med.

I dette eksempel vil vi overveje medarbejdere med det samme navn som lige:

@Test offentligt ugyldigt givenEmpArray_SortEmpArray_thenSortedArrayinNaturalOrder () {Arrays.sort (medarbejdere); assertTrue (Arrays.equals (medarbejdere, medarbejdere sorteret)); }

Du kan definere den naturlige rækkefølge for elementer ved at implementere en Sammenlignelig interface, som har sammenligne med() metode til sammenligning af nuværende objekt og objekt, der er sendt som et argument.

For at forstå dette tydeligt, lad os se et eksempel Medarbejder klasse, der implementerer Sammenlignelig Interface:

offentlig klasse Medarbejderimplementer Sammenlignelig {... @Override offentlige boolske lig (Objekt obj) {return ((Medarbejder) obj) .getName (). er lig med (getName ()); } @ Override public int CompareTo (Objekt o) {Medarbejder e = (Medarbejder) o; returner getName (). sammenlignTo (e.getName ()); }}

Generelt logikken til sammenligning vil blive skrevet metoden sammenligne med. Her sammenligner vi medarbejderordren eller navn af medarbejderfeltet. To medarbejdere vil være ens, hvis de har samme navn.

Nu hvornår Arrays.sort (medarbejdere); kaldes i ovenstående kode, vi ved nu, hvad der er logikken og rækkefølgen, der følger med at sortere medarbejderne efter alderen:

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

Vi kan se, at matrixen er sorteret efter medarbejderens navn - som nu bliver en naturlig ordre for Medarbejder Klasse.

6.2. Ved brug af Komparator

Lad os nu sortere elementerne ved hjælp af en Komparator interface implementering - hvor vi sender den anonyme indre klasse on-the-fly til Arrays.sort () API:

@Test offentlig ugyldighed givenIntegerArray_whenUsingSort_thenSortedArray () {Integer [] integers = ArrayUtils.toObject (toSort); Arrays.sort (heltal, ny komparator () {@ Overstyr offentlig int sammenligning (Heltal a, Heltal b) {return Heltal. Sammenligne (a, b);}}); assertTrue (Arrays.equals (heltal, ArrayUtils.toObject (sortedInts))); }

Lad os nu sortere medarbejdere baseret på løn - og videregive en anden komparatorimplementering:

Arrays.sort (medarbejdere, ny komparator () {@ Override offentlig int sammenligning (Medarbejder o1, Medarbejder o2) {return Double.compare (o1.getSalary (), o2.getSalary ());}});

De sorterede medarbejdere arrays baseret på løn vil være:

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

Bemærk, at vi kan bruge Collections.sort () på en lignende måde at sortere Liste og Sæt af objekter i naturlig eller brugerdefineret rækkefølge som beskrevet ovenfor for arrays.

7. Sortering med Lambdas

Start med Java 8, vi kan bruge Lambdas til at implementere Komparator Funktionelt interface.

Du kan se på Lambdas i Java 8-opskrivning for at børste op på syntaksen.

Lad os erstatte den gamle komparator:

Komparator c = ny Comparator () {@ Override offentlig int sammenligning (Heltal a, Heltal b) {return Heltal. Sammenligne (a, b); }}

Med den tilsvarende implementering ved hjælp af Lambda-udtryk:

Komparator c = (a, b) -> Heltal. Sammenligne (a, b);

Lad os endelig skrive testen:

@Test offentlig ugyldighed givenArray_whenUsingSortWithLambdas_thenSortedArray () {Integer [] integersToSort = ArrayUtils.toObject (toSort); Arrays.sort (heltalToSort, (a, b) -> {return Integer.compare (a, b);}); assertTrue (Arrays.equals (heltalToSort, ArrayUtils.toObject (sortedInts))); }

Som du kan se, en meget renere og mere kortfattet logik her.

8. Brug Comparator. Sammenligning og Comparator. DerefterComparing

Java 8 leveres med to nye API'er, der er nyttige til sortering - sammenligne () og derefterComparing () i Komparator interface.

Disse er ret praktiske til sammenkædning af flere forhold i Komparator.

Lad os overveje et scenario, hvor vi måske vil sammenligne Medarbejder ved alder og derefter af navn:

@Test offentlig ugyldighed givenArrayObjects_whenUsingComparing_thenSortedArrayObjects () {List medarbejdereListe = Arrays.asList (medarbejdere); medarbejdere.sort (Comparator.comparing (Medarbejder :: getAge)); assertTrue (Arrays.toString (workers.toArray ()) .equals (sortedArrayString)); }

I dette eksempel Medarbejder :: getAge er sorteringsnøglen til Komparator interface implementering af en funktionel interface med sammenligningsfunktion.

Her er en række medarbejdere efter sortering:

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

Her sorteres medarbejderne ud fra alder.

Vi kan se John og Jessica er i samme alder - hvilket betyder, at ordrelogikken nu skal tage deres navne i betragtning - hvilket vi kan opnå med derefterComparing ():

... medarbejder.sort (Comparator.comparing (Medarbejder :: getAge) .danComparing (Medarbejder :: getName)); ... 

Efter sortering med ovenstående kodestykke sorteres elementerne i medarbejderarray som:

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

Dermed sammenligne () og derefterComparing () definitivt gøre mere komplekse sorteringsscenarier meget renere at implementere.

9. Konklusion

I denne artikel så vi, hvordan vi kan anvende sortering på Array, Liste, Sætog Kort.

Vi så også en kort introduktion om, hvordan funktioner i Java 8 kunne være nyttige i sortering som brug af Lambdas, sammenligne () og derefterComparing () og parallelSort ().

Alle eksempler, der bruges i artiklen, er tilgængelige på GitHub.