Sortering i Java

1. Oversikt

Denne artikkelen vil illustrere hvordan du kan bruke sortering på Array, Liste, Sett og Kart i Java 7 og Java 8.

2. Sortering med Array

La oss starte med å sortere heltallmatriser først ved hjelp av Arrays.sort () metode.

Vi definerer følgende int matriser 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 komplett matrise

La oss nå bruke det enkle Array.sort () API:

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

Den usorterte matrisen er nå fullstendig sortert:

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

Som nevnt i den offisielle JavaDoc, Arrays.sort bruker dobbelt-pivot Quicksort på primitiver. Den tilbyr O (n log (n)) ytelse og er vanligvis raskere enn tradisjonelle (en-pivot) Quicksort-implementeringer. Imidlertid bruker den en stabil, adaptiv, iterativ implementering av mergesort-algoritme for Array av objekter.

2.2. Sortering av en del av en matrise

Arrays.sort har en til sortere APIer - som vi vil diskutere her:

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

Dette vil bare sortere en del av matrisen, mellom de to indeksene.

La oss ta en titt på et raskt eksempel:

@Test offentlig ugyldighet gittIntArray_whenUsingRangeSort_thenRangeSortedArray () {Arrays.sort (toSort, 3, 7); assertTrue (Arrays.equals (toSort, sortedRangeInts)); }

Sorteringen vil bare gjøres på følgende undergruppeelementer (toIndex ville være eksklusivt):

[255, 7, 88, 200]

Den resulterende sorterte undergruppen inkludert hovedmatrisen vil være:

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

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

Java 8 kommer med en ny API - parallelSort - med en lignende signatur til Arrays.sort () API:

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

Bak kulissene til parallelSort (), det deler opp matrisen i forskjellige underarrayer (i henhold til granularitet i algoritmen til parallelSort). Hver undergruppe er sortert etter Arrays.sort () i forskjellige tråder slik at sortere kan utføres parallelt og blir til slutt slått sammen som en sortert matrise.

Merk at ForJoin-fellesbassenget brukes til å utføre disse parallelle oppgavene og deretter slå sammen resultatene.

Resultatet av Arrays.parallelSort kommer til å være det samme som Array.sort selvfølgelig er det bare å utnytte multi-threading.

Til slutt er det lignende varianter av API Arrays.sort i Arrays.parallelSort også:

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

3. Sortering a Liste

La oss nå bruke Collections.sort () API i java.utils.Collections - å sortere en Liste av heltal:

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

De Liste før sortering vil inneholde følgende elementer:

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

Og naturlig, etter sortering:

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

Som nevnt i Oracle JavaDoc for Samlinger. Sort, den bruker en modifisert fusjonsort og tilbyr garantert n logg (n) opptreden.

4. Sortering a Sett

Neste, la oss bruke Collections.sort () å sortere en LinkedHashSet.

Vi bruker LinkedHashSet fordi den opprettholder innsettingsrekkefølgen.

Legg merke til hvordan, for å bruke sortere API i Samlingervi pakker først inn settet i en liste:

@Test offentlig ugyldighet givenSet_whenUsingSort_thenSortedSet () {Set integersSet = new LinkedHashSet (Ints.asList (toSort)); Sett descSortedIntegersSet = ny LinkedHashSet (Arrays.asList (nytt heltal [] {255, 200, 123, 89, 88, 66, 7, 5, 1})); Listeliste = ny ArrayList (heltall); Collections.sort (Comparator.reverseOrder ()); integersSet = new LinkedHashSet (liste); assertTrue (Arrays.equals (integersSet.toArray (), descSortedIntegersSet.toArray ())); }

De Comparator.reverseOrder () metoden reverserer bestillingen pålagt av den naturlige bestillingen.

5. Sortering Kart

I denne delen begynner vi å se på sortering av et kart - både etter nøkler og etter verdier.

La oss først definere kartet vi skal sortere:

@Før offentlige ugyldige initVariables () {.... HashMap-kart = nytt 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 Kart av Keys

Vi trekker nå ut nøklene og verdier oppføringer fra HashMap og sorter det ut fra verdiene til tastene i dette eksemplet:

@Test offentlig ugyldig givenMap_whenSortingByKeys_thenSortedMap () {Integer [] sortedKeys = new Integer [] {6, 12, 22, 55, 66, 77}; Liste oppføringer = ny ArrayList (map.entrySet ()); Collections.sort (oppføringer, ny Comparator() {@Override public int Compare (Entry o1, Entry o2) {return o1.getKey (). CompareTo (o2.getKey ()); }}); Map sortedMap = new LinkedHashMap (); for (Map.Entry entry: entries) {sortedMap.put (entry.getKey (), entry.getValue ()); } assertTrue (Arrays.equals (sortedMap.keySet (). toArray (), sortedKeys)); }

Legg merke til hvordan vi brukte LinkedHashMap mens du kopierer det sorterte Innganger basert på nøkler (fordi HashSet garanterer ikke rekkefølgen på nøklene).

De Kart før sortering:

[Nøkkel: 66, Verdi: Earl] [Nøkkel: 22, Verdi: Apple] [Nøkkel: 6, Verdi: Rocky] [Nøkkel: 55, Verdi: John] [Nøkkel: 12, Verdi: George] [Nøkkel: 77, Verdi: Perle]

De Kart etter sortering med tastene:

[Nøkkel: 6, Verdi: Rocky] [Nøkkel: 12, Verdi: George] [Nøkkel: 22, Verdi: Apple] [Nøkkel: 55, Verdi: John] [Nøkkel: 66, Verdi: Earl] [Nøkkel: 77, Verdi: Perle] 

5.2. Sortering Kart av verdier

Her skal vi sammenligne verdier av HashMap oppføringer for sortering basert på verdier av HashMap:

@Test offentlig ugyldighet gittMap_whenSortingByValues_thenSortedMap () {String [] sortedValues ​​= new String [] {"Apple", "Earl", "George", "John", "Pearl", "Rocky"}; Liste oppføringer = ny ArrayList (map.entrySet ()); Collections.sort (oppføringer, ny Comparator() {@Override public int Compare (Entry o1, Entry o2) {return o1.getValue (). CompareTo (o2.getValue ()); }}); Map sortedMap = new LinkedHashMap (); for (Map.Entry entry: entries) {sortedMap.put (entry.getKey (), entry.getValue ()); } assertTrue (Arrays.equals (sortedMap.values ​​(). toArray (), sortedValues)); }

De Kart før sortering:

[Nøkkel: 66, Verdi: Earl] [Nøkkel: 22, Verdi: Apple] [Nøkkel: 6, Verdi: Rocky] [Nøkkel: 55, Verdi: John] [Nøkkel: 12, Verdi: George] [Nøkkel: 77, Verdi: Perle]

De Kart etter sortering etter verdier:

[Nøkkel: 22, Verdi: Apple] [Nøkkel: 66, Verdi: Earl] [Nøkkel: 12, Verdi: George] [Nøkkel: 55, Verdi: John] [Nøkkel: 77, Verdi: Pearl] [Nøkkel: 6, Verdi: Rocky]

6. Sortering av egendefinerte objekter

La oss nå jobbe med et tilpasset objekt:

offentlig klasse Medarbeidere implementerer Sammenlignelig {privat strengnavn; privat alder; privat dobbeltlønn; offentlig ansatt (strengnavn, alder, dobbeltlønn) {...} // standard getters, setters and toString}

Vi bruker følgende Ansatt Array for sorteringseksempel i følgende seksjoner:

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

Vi kan sortere matriser eller samlinger av egendefinerte objekter enten:

  1. i naturlig rekkefølge (Bruke Sammenlignelig Grensesnitt) eller
  2. i rekkefølgen gitt av a KomparatorGrensesnitt

6.1. Usyng Sammenlignelig

Den naturlige rekkefølgen i java betyr en rekkefølge der primitive eller objekter skal ordnes ordnet i en gitt matrise eller samling.

Både java.util.Arrayer og java.util.Collections ha en sortere() metode, og Det anbefales på det sterkeste at naturlige ordrer skal være i samsvar med semantikken til er lik.

I dette eksemplet vil vi vurdere ansatte med det samme Navn like like:

@Test offentlig ugyldighet givenEmpArray_SortEmpArray_thenSortedArrayinNaturalOrder () {Arrays.sort (ansatte); assertTrue (Arrays.equals (ansatte, ansatte sortert)); }

Du kan definere den naturlige rekkefølgen for elementer ved å implementere en Sammenlignelig grensesnitt som har sammenligne med() metode for å sammenligne nåværende objekt og objekt sendt som argument.

For å forstå dette tydelig, la oss se et eksempel Ansatt klasse som implementerer Sammenlignelig Grensesnitt:

offentlig klasse Ansatt implementerer Sammenlignelig {... @Override offentlig boolsk er lik (Objekt obj) {retur ((Ansatt) obj) .getName (). er lik (getName ()); } @ Override public int CompareTo (Object o) {Employee e = (Employee) o; returner getName (). CompareTo (e.getName ()); }}

Generelt vil logikken for sammenligning bli skrevet metoden sammenligne med. Her sammenligner vi medarbeiderordren eller Navn av ansattfeltet. To ansatte vil være like hvis de har samme navn.

Nå når Arrays.sort (ansatte); kalles i koden ovenfor, vi vet nå hva som er logikken og rekkefølgen som går i å sortere de ansatte etter alder:

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

Vi kan se at matrisen er sortert etter navnet på den ansatte - som nå blir en naturlig ordre for Ansatt Klasse.

6.2. Ved hjelp av Komparator

La oss nå sortere elementene ved hjelp av a Komparator grensesnittimplementering - hvor vi sender den anonyme indre klassen on-the-fly til Arrays.sort () API:

@Test offentlig tomrom gittIntegerArray_whenUsingSort_thenSortedArray () {Heltall [] heltall = ArrayUtils.toObject (toSort); Arrays.sort (heltall, ny Comparator () {@ Override public int sammenligne (Heltall a, Heltall b) {return Heltall. Sammenligne (a, b);}}); assertTrue (Arrays.equals (heltall, ArrayUtils.toObject (sortedInts))); }

Nå kan vi sortere ansatte basert på lønn - og gi inn en annen komparatorimplementering:

Arrays.sort (ansatte, ny Comparator () {@Override offentlig int sammenligne (ansatt o1, ansatt o2) {return Double.compare (o1.getSalary (), o2.getSalary ());}});

De sorterte medarbeiderne arrays basert på lønn 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)] 

Merk at vi kan bruke Collections.sort () på en lignende måte å sortere Liste og Sett av objekter i naturlig eller tilpasset rekkefølge som beskrevet ovenfor for arrays.

7. Sortering med Lambdas

Start med Java 8, vi kan bruke Lambdas til å implementere Komparator Funksjonelt grensesnitt.

Du kan ta en titt på Lambdas i Java 8-skriving for å pusse opp syntaksen.

La oss erstatte den gamle komparatoren:

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

Med tilsvarende implementering, ved bruk av Lambda-uttrykk:

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

Til slutt, la oss skrive testen:

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

Som du kan se, en mye renere og mer kortfattet logikk her.

8. Bruke Comparator. Sammenligning og Comparator.thenComparing

Java 8 kommer med to nye APIer som er nyttige for sortering - sammenligne () og thenComparing () i Komparator grensesnitt.

Disse er ganske nyttige for kjetting av flere forhold i Komparator.

La oss vurdere et scenario der vi kanskje vil sammenligne Ansatt av alder og deretter av Navn:

@Test offentlig ugyldighet givenArrayObjects_whenUsingComparing_thenSortedArrayObjects () {List workersList = Arrays.asList (ansatte); ansatte.sort (Comparator.comparing (ansatt :: getAge)); assertTrue (Arrays.toString (ansatte.toArray ()) .equals (sortedArrayString)); }

I dette eksemplet, Ansatt :: getAge er sorteringsnøkkelen for Komparator grensesnitt implementerer et funksjonelt grensesnitt med sammenligningsfunksjon.

Her er utvalget av ansatte etter 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 de ansatte ut fra alder.

Vi kan se John og Jessica er på samme alder - som betyr at ordrelogikken nå skal ta hensyn til navnene deres - som vi kan oppnå med thenComparing ():

... ansatte.sort (Comparator.comparing (ansatt :: getAge) .thenComparing (ansatt :: getName)); ... 

Etter å ha sortert med kodebiten ovenfor, vil elementene i ansattes array sorteres 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)]

Og dermed sammenligne () og thenComparing () definitivt gjøre mer komplekse sorteringsscenarier mye renere å implementere.

9. Konklusjon

I denne artikkelen så vi hvordan vi kan bruke sortering på Array, Liste, Sett, og Kart.

Vi så også en kort introduksjon om hvordan funksjoner i Java 8 kan være nyttige i sortering som bruk av Lambdas, sammenligne () og thenComparing () og parallelSort ().

Alle eksempler som brukes i artikkelen er tilgjengelig på GitHub.


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