Triedenie v Jave
1. Prehľad
Tento článok ilustruje, ako použiť triedenie na Pole, Zoznam, Nastaviť a Mapa v prostredí Java 7 a Java 8.
2. Triedenie podľa Pole
Začnime najskôr zoradením celočíselných polí Arrays.sort () metóda.
Definujeme nasledujúce int polia v a @ Predtým Metóda jUnit:
@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}; sortRangeInts = new int [] {5, 1, 89, 7, 88, 200, 255, 123, 66}; ...}2.1. Triedenie je dokončené
Poďme teraz použiť jednoduché Array.sort () API:
@Test public void givenIntArray_whenUsingSort_thenSortedArray () {Arrays.sort (toSort); assertTrue (Arrays.equals (toSort, sortInts)); }Netriedené pole je teraz úplne zoradené:
[1, 5, 7, 66, 88, 89, 123, 200, 255]Ako je uvedené v oficiálnom dokumente JavaDoc, Polia. Zoradiť používa dual-pivot Quicksort na primitívi. Ponúka výkon O (n log (n)) a je zvyčajne rýchlejší ako tradičné implementácie Quicksort (s jedným pivotom). Používa však stabilnú, adaptívnu a iteratívnu implementáciu algoritmu mergesort pre Pole predmetov.
2.2. Triedenie časti poľa
Polia. Zoradiť má ešte jednu triediť API - o ktorých tu budeme diskutovať:
Arrays.sort (int [] a, int fromIndex, int toIndex)Takto sa zoradí iba časť poľa medzi týmito dvoma indexmi.
Pozrime sa na rýchly príklad:
@Test public void givenIntArray_whenUsingRangeSort_thenRangeSortedArray () {Arrays.sort (toSort, 3, 7); assertTrue (Arrays.equals (toSort, sortRangeInts)); }Triedenie sa uskutoční iba na nasledujúcich prvkoch čiastkového poľa (toIndex by bolo exkluzívne):
[255, 7, 88, 200]Výsledné zoradené čiastkové pole vrátane hlavného poľa by bolo:
[5, 1, 89, 7, 88, 200, 255, 123, 66]2.3. Java 8 Polia. Zoradiť vs Arrays.parallelSort
Java 8 prichádza s novým API - parallelSort - s podobným podpisom ako Arrays.sort () API:
@Test public void givenIntArray_whenUsingParallelSort_thenArraySorted () {Arrays.parallelSort (toSort); assertTrue (Arrays.equals (toSort, sortInts)); }V zákulisí parallelSort (), rozdeľuje pole na rôzne podradené polia (podľa granularity v algoritme parallelSort). Každé čiastkové pole je zoradené podľa Arrays.sort () v rôznych vláknach tak, aby triediť môžu byť vykonávané paralelne a sú nakoniec zlúčené ako triedené pole.
Všimnite si, že spoločný fond ForJoin sa používa na vykonávanie týchto paralelných úloh a následné zlúčenie výsledkov.
Výsledok Arrays.parallelSort bude rovnaké ako Pole. Zoradiť samozrejme, ide len o to, využiť multi-threading.
Nakoniec existujú podobné varianty API Polia. Zoradiť v Arrays.parallelSort tiež:
Arrays.parallelSort (int [] a, int fromIndex, int toIndex);3. Triedenie a Zoznam
Poďme teraz použiť Zbierka.sort () API v java.utils.Collections - triediť a Zoznam celých čísel:
@Test public void givenList_whenUsingSort_thenSortedList () {List toSortList = Ints.asList (toSort); Collections.sort (toSortList); assertTrue (Arrays.equals (toSortList.toArray (), ArrayUtils.toObject (sortInts)))); }The Zoznam pred triedením bude obsahovať nasledujúce prvky:
[5, 1, 89, 255, 7, 88, 200, 123, 66]A samozrejme, po zoradení:
[1, 5, 7, 66, 88, 89, 123, 200, 255]Ako je uvedené v Oracle JavaDoc pre Zbierky. Triediť, používa upravený zlúčený sortiment a garantované ponuky n log (n) výkon.
4. Triedenie a Nastaviť
Ďalej použijeme Zbierka.sort () triediť a LinkedHashSet.
Používame LinkedHashSet pretože zachováva poradie vloženia.
Všimnite si, ako na to, aby ste mohli používať triediť API v Zbierky – najskôr zabalíme súpravu do zoznamu:
@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})); Zoznam zoznam = new ArrayList (integersSet); Collections.sort (Comparator.reverseOrder ()); integersSet = nová LinkedHashSet (zoznam); assertTrue (Arrays.equals (integersSet.toArray (), descSortedIntegersSet.toArray ())); }The Comparator.reverseOrder () metóda obracia poradie uložené prirodzeným usporiadaním.
5. Triedenie Mapa
V tejto časti sa začneme zaoberať triedenie mapy - podľa kľúčov aj podľa hodnôt.
Najprv definujeme mapu, ktorú budeme triediť:
@ Pred verejnosťou void initVariables () {.... mapa HashMap = nová HashMap (); map.put (55, "John"); map.put (22, „Apple“); map.put (66, „gróf“); map.put (77, "Pearl"); map.put (12, "George"); map.put (6, „Rocky“); ....}5.1. Triedenie Mapa kľúčmi
Teraz budeme extrahovať kľúče a hodnoty záznamy z HashMap a zoraďte ich na základe hodnôt kľúčov v tomto príklade:
@Test public void givenMap_whenSortingByKeys_thenSortedMap () {Integer [] seřazenéKeys = nové celé číslo [] {6, 12, 22, 55, 66, 77}; Zoznam entries = new ArrayList (map.entrySet ()); Collections.sort (záznamy, nový porovnávač() {@Override public int compare (Záznam o1, Záznam o2) {return o1.getKey (). CompareTo (o2.getKey ()); }}); Mapa triedenáMapa = nová LinkedHashMap (); pre (položka Map.Entry: entries) {tříděnýMap.put (entry.getKey (), entry.getValue ()); } assertTrue (Arrays.equals (seřazenéMap.keySet (). toArray (), zoradenéKľúče)); } Všimnite si, ako sme použili LinkedHashMap pri kopírovaní vytriedeného Záznamy na základe kľúčov (pretože HashSet nezaručuje poradie kľúčov).
The Mapa pred triedením:
[Kľúč: 66, Hodnota: Earl] [Kľúč: 22, Hodnota: Apple] [Kľúč: 6, Hodnota: Rocky] [Kľúč: 55, Hodnota: John] [Kľúč: 12, Hodnota: George] [Kľúč: 77, Hodnota: Perla]The Mapa po triedení kľúčmi:
[Kľúč: 6, Hodnota: Rocky] [Kľúč: 12, Hodnota: George] [Kľúč: 22, Hodnota: Apple] [Kľúč: 55, Hodnota: John] [Kľúč: 66, Hodnota: Earl] [Kľúč: 77, Hodnota: Perla] 5.2. Triedenie Mapa podľa hodnôt
Tu budeme porovnávať hodnoty HashMap položky na triedenie na základe hodnôt HashMap:
@Test public void givenMap_whenSortingByValues_thenSortedMap () {String [] seřazenéHodnoty = nový String [] {"Apple", "Earl", "George", "John", "Pearl", "Rocky"}; Zoznam entries = new ArrayList (map.entrySet ()); Collections.sort (záznamy, nový porovnávač() {@Override public int compare (Záznam o1, Záznam o2) {return o1.getValue (). CompareTo (o2.getValue ()); }}); Mapa triedenáMapa = nová LinkedHashMap (); pre (položka Map.Entry: entries) {tříděnýMap.put (entry.getKey (), entry.getValue ()); } assertTrue (Arrays.equals (sortMap.values (). toArray (), triedenéHodnoty)); } The Mapa pred triedením:
[Kľúč: 66, Hodnota: Earl] [Kľúč: 22, Hodnota: Apple] [Kľúč: 6, Hodnota: Rocky] [Kľúč: 55, Hodnota: John] [Kľúč: 12, Hodnota: George] [Kľúč: 77, Hodnota: Perla]The Mapa po triedení hodnotami:
[Kľúč: 22, Hodnota: Apple] [Kľúč: 66, Hodnota: Earl] [Kľúč: 12, Hodnota: George] [Kľúč: 55, Hodnota: John] [Kľúč: 77, Hodnota: Pearl] [Kľúč: 6, Hodnota: skalnatý]6. Triedenie vlastných objektov
Poďme teraz pracovať s vlastným objektom:
public class Zamestnanec implementuje Comparable {private String name; súkromný int vek; dvojitý súkromný plat; public Employee (String name, int age, double plate) {...} // štandardní getri, setteri a toString}Budeme používať nasledujúce Zamestnanec Pole na triedenie príkladu v nasledujúcich častiach:
@Before public void initVariables () {.... zamestnanci = nový zamestnanec [] {nový zamestnanec („John“, 23, 5000), nový zamestnanec („Steve“, 26, 6000), nový zamestnanec („Frank“, 33, 7000), nový zamestnanec („Earl“, 43, 10 000), nový zamestnanec („Jessica“, 23, 4000), nový zamestnanec („Pearl“, 33, 6000)}; staffSorted = new Employee [] {new Employee ("Earl", 43, 10 000), new Employee ("Frank", 33, 70000), new Employee ("Jessica", 23, 4000), new Employee ("John", 23, 5000), nový zamestnanec („Pearl“, 33, 4000), nový zamestnanec („Steve“, 26, 6000)}; zamestnanciSortedByAge = nový zamestnanec [] {nový zamestnanec („John“, 23, 5000), nová zamestnankyňa („Jessica“, 23, 4000), nový zamestnanec („Steve“, 26, 6000), nový zamestnanec („Frank“, 33, 70000), nový zamestnanec („Pearl“, 33, 4000), nový zamestnanec („Earl“, 43, 10 000)}; }Polia alebo kolekcie vlastných objektov môžeme triediť buď:
- v prirodzenom poradí (pomocou Porovnateľné Rozhranie) alebo
- v poradí uvedenom a KomparátorRozhranie
6.1. Uspievať Porovnateľné
Prirodzené poradie v jave znamená poradie, v ktorom by mali byť primitívne objekty alebo objekty usporiadané v danom poli alebo zbierke.
Oboje java.util.Arrays a java.util.Collections mať sort () metóda a Dôrazne sa odporúča, aby prirodzené objednávky boli v súlade so sémantikou výrazu rovná sa.
V tomto príklade budeme brať do úvahy zamestnancov s rovnakými názov ako rovnocenné:
@Test public void givenEmpArray_SortEmpArray_thenSortedArrayinNaturalOrder () {Arrays.sort (zamestnanci); assertTrue (Arrays.equals (zamestnanci, zamestnanci zoradení)); }Prirodzené poradie prvkov môžete definovať implementáciou a Porovnateľné rozhranie, ktoré má porovnať s() metóda na porovnanie aktuálneho objektu a objektu odovzdaného ako argument.
Aby sme to jasne pochopili, pozrime sa na príklad Zamestnanec trieda, ktorá implementuje Porovnateľné Rozhranie:
public class Employee implements Comparable {... @Override public boolean equals (Object obj) {return ((Employee) obj) .getName (). equals (getName ()); } @Override public int compareTo (Object o) {Employee e = (Employee) o; návrat getName (). compareTo (e.getName ()); }}Logicky pre porovnanie bude všeobecne napísaná metóda porovnať s. Tu porovnávame objednávku zamestnancov resp názov zamestnaneckého poľa. Dvaja zamestnanci si budú rovní, ak majú rovnaké meno.
Teraz, keď Arrays.sort (zamestnanci); sa volá vo vyššie uvedenom kóde, teraz vieme, aká je logika a poriadok, ktorý platí pri triedení zamestnancov podľa veku:
[(„Earl“, 43 10000), („Frank“, 33, 70000), („Jessica“, 23, 4000), („John“, 23, 5000), („Pearl“, 33, 4000) , („Steve“, 26, 6000)]Vidíme, že pole je zoradené podľa mena zamestnanca - pre ktoré sa to teraz stáva prirodzeným poriadkom Zamestnanec Trieda.
6.2. Použitím Komparátor
Teraz poďme triediť prvky pomocou a Komparátor implementácia rozhrania - kde odovzdávame anonymnú vnútornú triedu priebežne do systému Arrays.sort () API:
@Test public void givenIntegerArray_whenUsingSort_thenSortedArray () {Integer [] integers = ArrayUtils.toObject (toSort); Arrays.sort (celé čísla, nový komparátor () {@Override public int compare (celé číslo a, celé číslo b) {návrat Integer.compare (a, b);}}); assertTrue (Arrays.equals (integers, ArrayUtils.toObject (orderedInts))); }Teraz umožňuje triediť zamestnancov na základe plat - a odovzdať ďalšiu implementáciu komparátora:
Arrays.sort (zamestnanci, nový komparátor () {@Override public int compare (zamestnanec o1, zamestnanec o2) {return Double.compare (o1.getSalary (), o2.getSalary ());}});Zoradené polia zamestnancov sú založené na plat bude:
[(Jessica, 23,4000,0), (John, 23,5000,0), (Pearl, 33,6000,0), (Steve, 26,6000,0), (Frank, 33,7000,0), (Earl, 43,10000,0)] Všimnite si, že môžeme použiť Zbierka.sort () podobným spôsobom triediť Zoznam a Nastaviť objektov v prírodnom alebo vlastnom poradí, ako je popísané vyššie pre polia.
7. Triedenie s lambdami
Začnite s Java 8, na implementáciu môžeme použiť Lambdas Komparátor Funkčné rozhranie.
Môžete sa pozrieť na zápis Lambdas v jazyku Java 8, aby ste oprášili syntax.
Vymeňme starý komparátor:
Komparátor c = nový komparátor () {@Override public int compare (Integer a, Integer b) {return Integer.compare (a, b); }}S ekvivalentnou implementáciou pomocou výrazu Lambda:
Komparátor c = (a, b) -> Integer.compare (a, b);Nakoniec napíšeme test:
@Test public void givenArray_whenUsingSortWithLambdas_thenSortedArray () {Integer [] integersToSort = ArrayUtils.toObject (toSort); Arrays.sort (integersToSort, (a, b) -> {return Integer.compare (a, b);}); assertTrue (Arrays.equals (integersToSort, ArrayUtils.toObject (triedenéInty))); }Ako vidíte, oveľa čistejšia a stručnejšia logika tu.
8. Používanie Comparator.comparing a Comparator.thenPorovnanie
Java 8 prichádza s dvoma novými API užitočnými na triedenie - porovnanie () a thenComparing () v Komparátor rozhranie.
Sú celkom užitočné na zreťazenie viacerých podmienok systému Komparátor.
Uvažujme o scenári, kde by sme mohli chcieť porovnávať Zamestnanec od Vek a potom názov:
@Test public void givenArrayObjects_whenUsingComparing_thenSortedArrayObjects () {Zoznam zamestnancovList = Arrays.asList (zamestnanci); zamestnanci.sort (Comparator.comparing (zamestnanec :: getAge)); assertTrue (Arrays.toString (zamestnanci.toArray ()) .equals (triedenéArrayString)); }V tomto príklade Zamestnanec :: getAge je triediaci kľúč pre Komparátor rozhranie implementujúce funkčné rozhranie s funkciou porovnania.
Tu je zoznam zamestnancov po zoradení:
[(John, 23,5000,0), (Jessica, 23,4000,0), (Steve, 26,6000,0), (Frank, 33,7000,0), (Pearl, 33,6000,0), (Earl, 43,10000,0)]Tu sú zamestnanci zoradení podľa Vek.
Môžeme vidieť Ján a Jessica sú rovnakého veku - čo znamená, že logika objednávok by teraz mala brať do úvahy ich mená - s čím môžeme dosiahnuť thenComparing ():
... employees.sort (Comparator.comparing (Employee :: getAge) .thenComparing (Employee :: getName)); ... Po zoradení pomocou vyššie uvedeného fragmentu kódu by boli prvky v poli zamestnancov zoradené ako:
[(Jessica, 23,4000,0), (John, 23,5000,0), (Steve, 26,6000,0), (Frank, 33,7000,0), (Pearl, 33,6000,0), (Earl, 43,10000,0)]Teda porovnanie () a thenComparing () určite urobte zložitejšie scenáre triedenia omnoho čistejšie na implementáciu.
9. Záver
V tomto článku sme videli, ako môžeme použiť triedenie na Pole, Zoznam, Nastaviťa Mapa.
Videli sme tiež krátky úvod o tom, ako by mohli byť funkcie Java 8 užitočné pri triedení, ako napríklad použitie Lambdas, porovnanie () a thenComparing () a parallelSort ().
Všetky príklady použité v článku sú k dispozícii na GitHub.
