Rendezés Java-ban

1. Áttekintés

Ez a cikk bemutatja, hogyan alkalmazható a rendezés Sor, Lista, Készlet és Térkép Java 7-ben és Java 8-ban.

2. Rendezés vele Sor

Kezdjük azzal, hogy először az egész tömböket rendezzük Tömbök. Rendezés () módszer.

Meghatározzuk a következőket int tömbök a @Előtt jUnit módszer:

@ Mielőtt nyilvános void 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. A teljes tömb rendezése

Használjuk most az egyszerűt Array.sort () API:

@Test public void givenIntArray_whenUsingSort_thenSortedArray () {Arrays.sort (toSort); assertTrue (Tömbök.egyenlő (toSort, sortedInts)); }

A nem rendezett tömb teljesen rendezve van:

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

Amint azt a hivatalos JavaDoc Tömbök.rendezés dual-pivot Quicksort alkalmazást használ primitívek. O (n log (n)) teljesítményt kínál, és jellemzően gyorsabb, mint a hagyományos (egycsuklós) Quicksort megvalósítások. Azonban a mergesort algoritmus stabil, adaptív, iteratív megvalósítását alkalmazza Sor objektumok.

2.2. Egy tömb egy részének rendezése

Tömbök.rendezés van még egy fajta API-k - amelyeket itt megvitatunk:

Tömbök. Rendezés (int [] a, int fromIndex, int toIndex)

Ez csak a tömb egy részét fogja rendezni a két index között.

Nézzünk meg egy gyors példát:

@Test public void givenIntArray_whenUsingRangeSort_thenRangeSortedArray () {Arrays.sort (toSort, 3, 7); assertTrue (tömbök.egyenlő (toSort, sortedRangeInts)); }

A rendezés csak a következő altömb-elemeken (toIndex kizárólagos lenne):

[255, 7, 88, 200]

A kapott rendezett altömb, beleértve a fő tömböt, a következő lenne:

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

2.3. Java 8 Tömbök.rendezés vs. Tömbök.parallelSort

A Java 8 új API-val érkezik - parallelSort - hasonló aláírással, mint a Tömbök. Rendezés () API:

@Test public void givenIntArray_whenUsingParallelSort_thenArraySorted () {Arrays.parallelSort (toSort); assertTrue (Tömbök.egyenlő (toSort, sortedInts)); }

A színfalak mögött parallelSort (), különböző tömbökre bontja a tömböt (a. algoritmusának részletessége szerint) parallelSort). Minden altömb rendezve van Tömbök. Rendezés () különböző szálakban úgy fajta párhuzamosan végrehajtható, és végül rendezett tömbként egyesül.

Ne feledje, hogy a ForJoin közös készlet használható ezeknek a párhuzamos feladatoknak a végrehajtására, majd az eredmények összevonására.

Az eredmény Tömbök.parallelSort ugyanaz lesz, mint Tömb.válogatás természetesen csak a többszálas kihasználás kérdése.

Végül vannak az API hasonló változatai Tömbök.rendezés ban ben Tömbök.parallelSort is:

Tömbök.parallelSort (int [] a, int fromIndex, int toIndex);

3. Rendezés a Lista

Most használjuk a Collections.sort () API in java.utils.Kollekciók - rendezni a Lista egész számok:

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

A Lista a rendezés előtt a következő elemeket tartalmazza:

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

És természetesen a válogatás után:

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

Amint azt az Oracle JavaDoc for Gyűjtemények. Rendezés, módosított mergesort alkalmaz és garantált ajánlatokat kínál n log (n) teljesítmény.

4. Rendezés a Készlet

Ezután használjuk Collections.sort () rendezni a LinkedHashSet.

Használjuk a LinkedHashSet mert fenntartja a beszúrási rendet.

Figyelje meg, hogyan kell használni a fajta API in Gyűjteményekelőször csomagoljuk be a készletet egy listába:

@Test public void givenSet_whenUsingSort_thenSortedSet () {Set integersSet = new LinkedHashSet (Ints.asList (toSort)); Set descSortedIntegersSet = new LinkedHashSet (Arrays.asList (new Integer [] {255, 200, 123, 89, 88, 66, 7, 5, 1})); Lista lista = new ArrayList (integersSet); Collections.sort (Összehasonlító.reverseOrder ()); integersSet = új LinkedHashSet (lista); assertTrue (Tömbök.egyenlő (integersSet.toArray (), descSortedIntegersSet.toArray ())); }

A Comparator.reverseOrder () módszer megfordítja a természetes rendezés által előírt sorrendet.

5. Rendezés Térkép

Ebben a részben elkezdjük vizsgálni Térkép rendezése - kulcsok és értékek szerint is.

Először határozzuk meg a rendezni kívánt térképet:

@A nyilvános void előtt initVariables () {.... HashMap map = new HashMap (); map.put (55, "John"); map.put (22, "Apple"); map.put (66, "Earl"); map.put (77, "Gyöngy"); map.put (12, "George"); map.put (6, "Sziklás"); ....}

5.1. Válogató Térkép írta Keys

Most kivonjuk kulcsok és értékek bejegyzések a HashMap és rendezze az ebben a példában szereplő kulcsok értéke alapján:

@Test public void givenMap_whenSortingByKeys_thenSortedMap () {Egész szám [] sortedKeys = új Egész szám [] {6, 12, 22, 55, 66, 77}; Lista bejegyzések = új ArrayList (map.entrySet ()); Collections.sort (bejegyzések, új Comparator() {@Orride public int összehasonlítás (o1 bejegyzés, o2 bejegyzés) {return o1.getKey (). CompareTo (o2.getKey ()); }}); Map sortedMap = new LinkedHashMap (); a (Map.Entry bejegyzés: bejegyzések) {sortedMap.put (entry.getKey (), entry.getValue ()); } assertTrue (Tömbök.egyenlő (sortedMap.keySet (). toArray (), sortedKeys)); }

Vegye figyelembe, hogyan használtuk a LinkedHashMap miközben másolja a rendezett Bejegyzés kulcsok alapján (mert HashSet nem garantálja a kulcsok sorrendjét).

A Térkép válogatás előtt:

[Kulcs: 66, Érték: Earl] [Kulcs: 22, Érték: Alma] [Kulcs: 6, Érték: Sziklás] [Kulcs: 55, Érték: János] [Kulcs: 12, Érték: George] [Kulcs: 77, Érték: Gyöngy]

A Térkép válogatás után gombokkal:

[Kulcs: 6, Érték: Sziklás] [Kulcs: 12, Érték: George] [Kulcs: 22, Érték: Alma] [Kulcs: 55, Érték: János] [Kulcs: 66, Érték: Earl] [Kulcs: 77, Érték: Gyöngy] 

5.2. Válogató Térkép értékek szerint

Itt összehasonlítjuk a HashMap értékei alapján rendezésre szolgáló bejegyzések HashMap:

@Test public void givenMap_whenSortingByValues_thenSortedMap () {String [] sortedValues ​​= new String [] {"Apple", "Earl", "George", "John", "Pearl", "Rocky"}; Lista bejegyzések = új ArrayList (map.entrySet ()); Collections.sort (bejegyzések, új Comparator() {@Orride public int összehasonlítás (o1 bejegyzés, o2 bejegyzés) {return o1.getValue (). CompareTo (o2.getValue ()); }}); Map sortedMap = new LinkedHashMap (); a (Map.Entry bejegyzés: bejegyzések) {sortedMap.put (entry.getKey (), entry.getValue ()); } assertTrue (Tömbök.egyenlő (sortedMap.values ​​(). toArray (), sortedValues)); }

A Térkép válogatás előtt:

[Kulcs: 66, Érték: Earl] [Kulcs: 22, Érték: Alma] [Kulcs: 6, Érték: Sziklás] [Kulcs: 55, Érték: János] [Kulcs: 12, Érték: George] [Kulcs: 77, Érték: Gyöngy]

A Térkép válogatás után értékek szerint:

[Kulcs: 22, Érték: Apple] [Kulcs: 66, Érték: Earl] [Kulcs: 12, Érték: George] [Kulcs: 55, Érték: John] [Kulcs: 77, Érték: Gyöngy] [Kulcs: 6, Érték: Sziklás]

6. Egyéni objektumok rendezése

Most dolgozzunk egy egyedi objektummal:

public class Alkalmazott megvalósítja összehasonlítható {privát karakterlánc neve; privát int kor; magán kettős fizetés; közalkalmazott (karakterlánc neve, kora, dupla fizetés) {...} // szokásos getterek, beállítók és toString}

A következőket fogjuk használni Munkavállaló A rendezési példa tömbje a következő szakaszokban:

@A nyilvános void előtt initVariables () {.... alkalmazottak = új alkalmazott [] {új alkalmazott ("John", 5000, 23), új alkalmazott ("Steve", 26, 6000), új alkalmazott ("Frank", 33, 7000), új alkalmazott ("Earl", 43, 10000), új alkalmazott ("Jessica", 4000, 23), új alkalmazott ("Pearl", 33, 6000)}; alkalmazottokSorted = new Employee [] {new Employee ("Earl", 43, 10000), new Employee ("Frank", 33, 70000), new Employee ("Jessica", 4000, 23), new Employee ("John", 23., 5000), új alkalmazott ("Pearl", 33, 4000), új alkalmazott ("Steve", 26, 6000)}; alkalmazottaiSortedByAge = új alkalmazott [] {új alkalmazott ("John", 23, 5000), új alkalmazott ("Jessica", 4000, 23), új alkalmazott ("Steve", 26, 6000), új alkalmazott ("Frank", 33, 70000), új alkalmazott ("Pearl", 33, 4000), új alkalmazott ("Earl", 43, 10000)}; }

Rendezhetünk tömböket vagy egyedi objektumok gyűjteményeit:

  1. természetes sorrendben (A Hasonló Interfész) vagy
  2. által biztosított sorrendben ÖsszehasonlítóFelület

6.1. Uénekelj összehasonlítható

A java természetes rendje azt a sorrendet jelenti, amelyben a primitívet vagy az Objektumot rendezetten kell rendezni egy adott tömbben vagy gyűjteményben.

Mindkét java.util.A Arrays és java.util.Kollekciók Van egy fajta() módszer, és Nagyon ajánlott, hogy a természetes sorrendeknek összhangban kell lenniük a egyenlő.

Ebben a példában az alkalmazottakat vesszük figyelembe név egyenlő:

@Test public void givenEmpArray_SortEmpArray_thenSortedArrayinNaturalOrder () {Arrays.sort (alkalmazottak); assertTrue (tömbök. egyenlő (alkalmazottak, alkalmazottak rendezve)); }

Az a megvalósításával meghatározhatja az elemek természetes sorrendjét Hasonló interfész, amely rendelkezik összehasonlítani() módszer az aktuális objektum és az argumentumként átadott objektum összehasonlítására.

Ennek egyértelmű megértéséhez lássunk egy példát Munkavállaló osztály, amely megvalósítja Hasonló Felület:

public class Alkalmazott megvalósítja Összehasonlítható {... @Orride public boolean equals (Object obj) {return ((Employee) obj) .getName (). equals (getName ()); } @Orride public int CompareTo (o objektum) {Employee e = (Employee) o; return getName (). összehasonlít (e.getName ()); }}

Általában az összehasonlítás logikája írja le a módszert összehasonlítani. Itt összehasonlítjuk a munkavállalói megrendelést ill név az alkalmazottak területén. Két alkalmazott egyenlő lesz, ha ugyanaz a neve.

Most mikor Tömbök.rendezés (alkalmazottak); a fenti kódban hívják, most már tudjuk, mi a logika és a sorrend az alkalmazottak életkor szerinti rendezésében:

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

Láthatjuk, hogy a tömb az alkalmazott neve szerint van rendezve - ami most már természetes megrendeléssé válik Munkavállaló Osztály.

6.2. Használata Összehasonlító

Most rendezzük az elemeket a használatával Összehasonlító interfész megvalósítás - ahol az anonim belső osztályt menet közben átadjuk a Tömbök. Rendezés () API:

@Test public void givenIntegerArray_whenUsingSort_thenSortedArray () {Egész szám [] egész szám = ArrayUtils.toObject (toSort); Tömbök.sort (egész számok, új Comparator () {@Orride public int összehasonlítás (Integer a, Integer b) {return Integer.compare (a, b);}}; assertTrue (Tömbök.egyenlő (egész számok, ArrayUtils.toObject (sortedInts))); }

Most lehetővé teszi az alkalmazottak rendezését fizetés - és átkerül egy másik összehasonlító megvalósításba:

Tömbök.sort (alkalmazottak, új Comparator () {@Orride public int összehasonlítás (o1 alkalmazott, o2 alkalmazott) {return Double.compare (o1.getSalary (), o2.getSalary ());}});

A rendezett Employees tömbök alapján fizetés lesz:

[(Jessica, 23.4000,0), (John, 23.5000.0), (Pearl, 33.6000.0), (Steve, 26.6000.0), (Frank, 33.7000.0), (Earl, 43.10000.0)] 

Vegye figyelembe, hogy használhatjuk Collections.sort () hasonló módon válogatni Lista és Készlet objektumok természetes vagy egyedi sorrendben, a tömböknél fent leírtak szerint.

7. Válogatás a lambdákkal

Kezdje a Java 8-zal, a Lambdas-t használhatjuk a Összehasonlító Funkcionális interfész.

Megtekintheti a Lambdas in Java 8 felírást, hogy feljavítsa a szintaxist.

Cseréljük ki a régi összehasonlítót:

C = új összehasonlító () Comparator () {@Orride public int összehasonlítás (Integer a, Integer b) {return Integer.compare (a, b); }}

Ezzel egyenértékű megvalósítással, a Lambda kifejezés használatával:

C) összehasonlító = (a, b) -> Egész. Összehasonlítás (a, b);

Végül írjuk meg a tesztet:

@Test public void givenArray_whenUsingSortWithLambdas_thenSortedArray () {Egész szám [] integersToSort = ArrayUtils.toObject (toSort); Tömbök.sort (integersToSort, (a, b) -> {return Integer.compare (a, b);}); assertTrue (Tömbök.egyenlő (integersToSort, ArrayUtils.toObject (sortedInts))); }

Amint láthatja, itt sokkal tisztább és tömörebb logika.

8. Használata Összehasonlító.összehasonlítás és Összehasonlító.akkor Összehasonlítás

A Java 8 két új API-val rendelkezik, amelyek hasznosak a rendezéshez - összehasonlítás () és thenComparing () ban,-ben Összehasonlító felület.

Ezek meglehetősen hasznosak a Összehasonlító.

Vegyünk egy forgatókönyvet, ahol érdemes összehasonlítani Munkavállaló által kor majd által név:

@Test public void givenArrayObjects_whenUsingComparing_thenSortedArrayObjects () {List usersList = Arrays.asList (alkalmazottak); alkalmazottak.válogatás (Comparator.comparing (Employee :: getAge)); assertTrue (Arrays.toString (alkalmazottak.toArray ()) .egyenlő (sortedArrayString)); }

Ebben a példában Alkalmazott :: getAge a rendezési kulcs Összehasonlító interfész funkcionális interfészt valósít meg összehasonlító funkcióval.

Íme az alkalmazottak tömbje válogatás után:

[(John, 23.5000,0), (Jessica, 23.4000.0), (Steve, 26.6000.0), (Frank, 33.7000.0), (Pearl, 33.6000.0), (Earl, 43.10000.0)]

Itt az alkalmazottak sorrendje alapján kor.

Láthatjuk János és Jessica egyidősek - ami azt jelenti, hogy a sorrend logikának most figyelembe kell venniük a nevüket - amellyel elérhetjük thenComparing ():

... alkalmazottak.válogatás (Comparator.comparing (Employee :: getAge) .thenComparing (Employee :: getName)); ... 

A fenti kódrészlettel történő rendezés után az alkalmazotti tömb elemei a következők lesznek rendezve:

[(Jessica, 23.4000,0), (John, 23.5000.0), (Steve, 26.6000.0), (Frank, 33.7000.0), (Pearl, 33.6000.0), (Earl, 43.10000.0)]

Így összehasonlítás () és thenComparing () a bonyolultabb rendezési szcenáriókat mindenképpen sokkal tisztábbá kell tenni.

9. Következtetés

Ebben a cikkben láttuk, hogyan alkalmazhatjuk a rendezést Sor, Lista, Készlet, és Térkép.

Láttunk egy rövid bevezetést arról is, hogy a Java 8 szolgáltatásai miként lehetnek hasznosak a rendezésben, például a Lambdas használata, összehasonlítás () és thenComparing () és parallelSort ().

A cikkben használt összes példa elérhető a GitHub oldalon.