Razvrstavanje u Javi
1. Pregled
Ovaj će članak ilustrirati kako primijeniti sortiranje na Polje, Popis, Postavi i Karta u Javi 7 i Javi 8.
2. Razvrstavanje s Polje
Počnimo s razvrstavanjem cjelovitih nizova koji su prvo korišteni Nizovi.sort () metoda.
Definirat ćemo sljedeće int nizovi u a @Prije jUnit metoda:
@Prije javne void initVariables () {toSort = new int [] {5, 1, 89, 255, 7, 88, 200, 123, 66}; sortedInts = novi int [] {1, 5, 7, 66, 88, 89, 123, 200, 255}; sortedRangeInts = new int [] {5, 1, 89, 7, 88, 200, 255, 123, 66}; ...}2.1. Sortiranje kompletnog niza
Koristimo sada jednostavno Array.sort () API:
@Test javna praznina givenIntArray_whenUsingSort_thenSortedArray () {Arrays.sort (toSort); assertTrue (Arrays.equals (toSort, sortedInts)); }Nerazvrstani niz sada je u potpunosti sortiran:
[1, 5, 7, 66, 88, 89, 123, 200, 255]Kao što je spomenuto u službenom JavaDocu, Nizovi.sort koristi dvostruki pivot Quicksort na primitivci. Nudi izvedbu O (n log (n)) i obično je brži od tradicionalnih (s jednim pivotom) Quicksort implementacija. Međutim, koristi stabilnu, prilagodljivu, iterativnu implementaciju mergesort algoritma za Polje predmeta.
2.2. Sortiranje dijela niza
Nizovi.sort ima još jedan vrsta API-ji - o kojima ćemo ovdje razgovarati:
Arrays.sort (int [] a, int fromIndex, int toIndex)Ovo će sortirati samo dio niza, između dva indeksa.
Pogledajmo kratki primjer:
@Test javna praznina givenIntArray_whenUsingRangeSort_thenRangeSortedArray () {Arrays.sort (toSort, 3, 7); assertTrue (Arrays.equals (toSort, sortedRangeInts)); }Razvrstavanje će se izvršiti samo na sljedećim elementima podniza (toIndex bilo bi ekskluzivno):
[255, 7, 88, 200]Rezultirajući sortirani podskup, uključujući glavni niz, bio bi:
[5, 1, 89, 7, 88, 200, 255, 123, 66]2.3. Java 8 Nizovi.sort nasuprot Nizovi.parallelSort
Java 8 dolazi s novim API-jem - paralelnoSort - sa sličnim potpisom na Nizovi.sort () API:
@Test javna praznina givenIntArray_whenUsingParallelSort_thenArraySorted () {Arrays.parallelSort (toSort); assertTrue (Arrays.equals (toSort, sortedInts)); }Iza kulisa paralelnoSort (), razbija niz na različite podnizove (prema granularnosti u algoritmu paralelnoSort). Svaki pod-niz sortiran je s Nizovi.sort () u različitim nitima tako da vrsta mogu se izvršiti paralelno i konačno spajati kao razvrstani niz.
Imajte na umu da se zajednički bazen ForJoin koristi za izvršavanje ovih paralelnih zadataka, a zatim za spajanje rezultata.
Rezultat Nizovi.parallelSort bit će isto što i Niz.razvrstaj naravno, stvar je samo u iskorištavanju više navoja.
Napokon, postoje slične inačice API-ja Nizovi.sort u Nizovi.parallelSort također:
Arrays.parallelSort (int [] a, int fromIndex, int toIndex);3. Sortiranje a Popis
Koristimo sada Collections.sort () API u java.utils.Zbirke - razvrstati a Popis cijelih brojeva:
@Test javna praznina givenList_whenUsingSort_thenSortedList () {Popis toSortList = Ints.asList (toSort); Collections.sort (toSortList); assertTrue (Arrays.equals (toSortList.toArray (), ArrayUtils.toObject (sortedInts))); }The Popis prije sortiranja sadržavat će sljedeće elemente:
[5, 1, 89, 255, 7, 88, 200, 123, 66]I naravno, nakon sortiranja:
[1, 5, 7, 66, 88, 89, 123, 200, 255]Kao što je spomenuto u Oracle JavaDoc za Zbirke.Razvrstaj, koristi modificirani spoj i nudi zajamčene ponude n zapisnik (n) izvođenje.
4. Sortiranje a Postavi
Dalje, poslužimo se Collections.sort () razvrstati a LinkedHashSet.
Koristimo LinkedHashSet jer održava redoslijed umetanja.
Primijetite kako, da biste koristili vrsta API u Zbirke – prvo umotavamo set u popis:
@Test public void givenSet_whenUsingSort_thenSortedSet () {Set integersSet = new LinkedHashSet (Ints.asList (toSort)); Postavi descSortedIntegersSet = novi LinkedHashSet (Arrays.asList (novi Integer [] {255, 200, 123, 89, 88, 66, 7, 5, 1})); Lista popisa = novi ArrayList (integersSet); Collections.sort (Comparator.reverseOrder ()); integersSet = novi LinkedHashSet (popis); assertTrue (Arrays.equals (integersSet.toArray (), descSortedIntegersSet.toArray ())); }The Usporednik.reverseOrder () metoda preokreće poredak nametnut prirodnim uređenjem.
5. Sortiranje Karta
U ovom ćemo dijelu započeti s proučavanjem sortiranje karte - i po ključevima i po vrijednostima.
Prvo definirajmo kartu koju ćemo sortirati:
@Prije javne void initVariables () {.... HashMap karta = nova HashMap (); map.put (55, "Ivan"); map.put (22, "Apple"); map.put (66, "Earl"); map.put (77, "Biser"); map.put (12, "George"); map.put (6, "Rocky"); ....}5.1. Sortiranje Karta od Keysa
Sad ćemo izdvojiti tipke i vrijednosti unosi iz HashMap i sortirajte ga na temelju vrijednosti ključeva u ovom primjeru:
@Test javna praznina givenMap_whenSortingByKeys_thenSortedMap () {Integer [] sortedKeys = new Integer [] {6, 12, 22, 55, 66, 77}; Popis unosi = novi ArrayList (map.entrySet ()); Collections.sort (unosi, novi Usporednik() {@Override public int compare (Entry o1, Entry o2) {return o1.getKey (). CompareTo (o2.getKey ()); }}); Karta sortedMap = new LinkedHashMap (); za (Map.Entry entry: entries) {sortedMap.put (entry.getKey (), entry.getValue ()); } assertTrue (Arrays.equals (sortedMap.keySet (). toArray (), sortedKeys)); } Primijetite kako smo koristili LinkedHashMap dok kopirate razvrstano Unosi na temelju ključeva (jer HashSet ne jamči redoslijed ključeva).
The Karta prije sortiranja:
[Ključ: 66, Vrijednost: Earl] [Ključ: 22, Vrijednost: Apple] [Ključ: 6, Vrijednost: Rocky] [Ključ: 55, Vrijednost: John] [Ključ: 12, Vrijednost: George] [Ključ: 77, Vrijednost: biser]The Karta nakon sortiranja po ključevima:
[Key: 6, Value: Rocky] [Key: 12, Value: George] [Key: 22, Value: Apple] [Key: 55, Value: John] [Key: 66, Value: Earl] [Key: 77, Vrijednost: biser] 5.2. Sortiranje Karta po Vrijednostima
Ovdje ćemo usporediti vrijednosti HashMap unosi za sortiranje na temelju vrijednosti HashMap:
@Test javna praznina givenMap_whenSortingByValues_thenSortedMap () {String [] sortedValues = new String [] {"Apple", "Earl", "George", "John", "Pearl", "Rocky"}; Popis unosi = novi ArrayList (map.entrySet ()); Collections.sort (unosi, novi Usporednik() {@Override public int compare (Entry o1, Entry o2) {return o1.getValue (). CompareTo (o2.getValue ()); }}); Karta sortedMap = new LinkedHashMap (); za (Map.Entry entry: entries) {sortedMap.put (entry.getKey (), entry.getValue ()); } assertTrue (Arrays.equals (sortedMap.values (). toArray (), sortedValues)); } The Karta prije sortiranja:
[Ključ: 66, Vrijednost: Earl] [Ključ: 22, Vrijednost: Apple] [Ključ: 6, Vrijednost: Rocky] [Ključ: 55, Vrijednost: John] [Ključ: 12, Vrijednost: George] [Ključ: 77, Vrijednost: biser]The Karta nakon sortiranja po vrijednostima:
[Ključ: 22, Vrijednost: Apple] [Ključ: 66, Vrijednost: Earl] [Ključ: 12, Vrijednost: George] [Ključ: 55, Vrijednost: John] [Ključ: 77, Vrijednost: Biser] [Ključ: 6, Vrijednost: Rocky]6. Sortiranje prilagođenih objekata
Ajmo sada raditi s prilagođenim objektom:
javna klasa Zaposlenik implementira Usporedivo {ime privatnog niza; privatno int doba; privatna dvostruka plaća; javni zaposlenik (ime niza, int starost, dvostruka plaća) {...} // standardni getters, setters i toString}Koristit ćemo sljedeće Zaposlenik Primjer niza za sortiranje u sljedećim odjeljcima:
@Before public void initVariables () {.... zaposlenici = novi zaposlenik [] {novi zaposlenik ("John", 23, 5000), novi zaposlenik ("Steve", 26, 6000), novi zaposlenik ("Frank", 33, 7000), novi zaposlenik ("Earl", 43, 10000), novi zaposlenik ("Jessica", 23, 4000), novi zaposlenik ("Biser", 33, 6000)}; zaposleniciSorted = novi zaposlenik [] {novi zaposlenik ("Earl", 43, 10000), novi zaposlenik ("Frank", 33, 70000), novi zaposlenik ("Jessica", 23, 4000), novi zaposlenik ("John", 23, 5000), novi zaposlenik ("Biser", 33, 4000), novi zaposlenik ("Steve", 26, 6000)}; zaposleniciSortedByAge = novi zaposlenik [] {novi zaposlenik ("John", 23, 5000), novi zaposlenik ("Jessica", 23, 4000), novi zaposlenik ("Steve", 26, 6000), novi zaposlenik ("Frank", 33, 70000), novi zaposlenik ("Biser", 33, 4000), novi zaposlenik ("grof", 43, 10000)}; }Možemo sortirati nizove ili kolekcije prilagođenih objekata:
- u prirodnom redoslijedu (Korištenje Usporedive Sučelje) ili
- redom predviđenim a UsporednikSučelje
6.1. Upjevaj Usporedivo
Prirodni poredak u javi znači redoslijed u kojem primitiv ili objekt treba uredno sortirati u danom nizu ili zbirci.
Oba java.util.Arrays i java.util.Zbirke imati vrsta() metoda i Preporučujemo da prirodni redoslijedi budu u skladu sa semantikom jednako.
U ovom ćemo primjeru razmotriti zaposlenike s istim Ime jednako:
@Test javna praznina givenEmpArray_SortEmpArray_thenSortedArrayinNaturalOrder () {Arrays.sort (zaposlenici); assertTrue (Arrays.equals (zaposlenici, zaposleniciSortirano)); }Prirodni redoslijed elemenata možete definirati primjenom a Usporedive sučelje koje ima compareTo () metoda za usporedbu trenutnog objekta i objekta prosljeđenog kao argument.
Da bismo to jasno razumjeli, pogledajmo primjer Zaposlenik razred koji provodi Usporedive Sučelje:
javna klasa Zaposlenik implementira Usporedivo {... @Override public boolean equals (Object obj) {return ((Employee) obj) .getName (). equals (getName ()); } @Override public int compareTo (Objekt o) {Zaposlenik e = (Zaposlenik) o; vrati getName (). compareTo (e.getName ()); }}Općenito, logika za usporedbu bit će napisana kao metoda usporediTo. Ovdje uspoređujemo redoslijed zaposlenika ili Ime polja zaposlenika. Dvoje zaposlenika bit će ravnopravno ako imaju isto ime.
Sad kad Nizovi.sort (zaposlenici); naziva se u gornjem kodu, sada znamo koja je logika i redoslijed sortiranja zaposlenika prema dobi:
[("Earl", 43, 10000), ("Frank", 33, 70000), ("Jessica", 23, 4000), ("John", 23, 5000), ("Biser", 33, 4000) , ("Steve", 26, 6000)]Vidimo da je niz sortiran po imenu zaposlenika - što sada postaje prirodni poredak za Zaposlenik Razred.
6.2. Koristeći Usporednik
Idemo sada sortirati elemente pomoću a Usporednik implementacija sučelja - gdje anonimnu unutarnju klasu u hodu prenosimo u letu Nizovi.sort () API:
@Test javna praznina givenIntegerArray_whenUsingSort_thenSortedArray () {Integer [] integers = ArrayUtils.toObject (toSort); Arrays.sort (integers, new Comparator () {@Preuzmi public int compare (Integer a, Integer b) {return Integer.compare (a, b);}}); assertTrue (Arrays.equals (integers, ArrayUtils.toObject (sortedInts))); }Sada omogućuje sortiranje zaposlenika prema plaća - i proslijedite u drugu implementaciju usporedbe:
Arrays.sort (zaposlenici, novi Komparator () {@Preuzmi javno int uspoređivanje (zaposlenik o1, zaposlenik o2) {return Double.compare (o1.getSalary (), o2.getSalary ());}});Sortirani nizovi zaposlenika temeljeni na plaća bit će:
[(Jessica, 23,4000.0), (John, 23,5000.0), (Pearl, 33,6000.0), (Steve, 26,6000.0), (Frank, 33,7000.0), (Earl, 43,10000.0)] Imajte na umu da možemo koristiti Collections.sort () na sličan način za sortiranje Popis i Postavi objekata u prirodnom ili prilagođenom redoslijedu kako je gore opisano za nizove.
7. Razvrstavanje s lambdama
Započnite s Javom 8, možemo koristiti Lambdas za implementaciju Usporednik Funkcionalno sučelje.
Možete pogledati Lambdas u Java 8 zapisu kako biste razjasnili sintaksu.
Zamijenimo staru usporedbu:
Usporednik c = novi Usporeditelj () {@Preuzmi javno int uspoređivanje (Integer a, Integer b) {return Integer.compare (a, b); }}S ekvivalentnom implementacijom, koristeći Lambda izraz:
Usporednik c = (a, b) -> Integer.compare (a, b);Na kraju, napišimo test:
@Test javna praznina givenArray_whenUsingSortWithLambdas_thenSortedArray () {Integer [] integersToSort = ArrayUtils.toObject (toSort); Arrays.sort (integersToSort, (a, b) -> {return Integer.compare (a, b);}); assertTrue (Arrays.equals (integersToSort, ArrayUtils.toObject (sortedInts))); }Kao što vidite, ovdje je puno čišća i sažetija logika.
8. Korištenje Usporednik.usporedba i Usporednik.potom Usporedba
Java 8 dolazi s dva nova API-ja korisna za sortiranje - uspoređivanje () i thenCombaring () u Usporednik sučelje.
To su vrlo zgodne za ulančavanje višestrukih uvjeta Usporednik.
Razmotrimo scenarij u kojem bismo mogli željeti usporediti Zaposlenik po dob a zatim po Ime:
@Test javna praznina givenArrayObjects_whenUsingComparing_thenSortedArrayObjects () {Popis zaposlenihList = Arrays.asList (zaposlenici); zaposlenici.sort (Comparator.comparing (Employee :: getAge)); assertTrue (Arrays.toString (zaposlenici.toArray ()) .equals (sortedArrayString)); }U ovom primjeru, Zaposlenik :: getAge je ključ za sortiranje za Usporednik sučelje koje implementira funkcionalno sučelje s funkcijom uspoređivanja.
Evo niza zaposlenika nakon sortiranja:
[(John, 23.5000,0), (Jessica, 23.4000.0), (Steve, 26.6000.0), (Frank, 33.7000.0), (Pearl, 33.6000.0), (Earl, 43.10000.0)]Ovdje se zaposlenici sortiraju prema dob.
Možemo vidjeti Ivan i Jessica su iste dobi - što znači da bi logika poretka sada trebala uzeti u obzir njihova imena - što možemo postići thenCombaring ():
... zaposlenici.sort (Comparator.comparing (Employee :: getAge) .thenComparing (Employee :: getName)); ... Nakon sortiranja s gornjim isječkom koda, elementi u polju zaposlenika sortirat će se kao:
[(Jessica, 23,4000.0), (John, 23,5000.0), (Steve, 26,6000.0), (Frank, 33,7000.0), (Pearl, 33,6000.0), (Earl, 43,10000.0)]Tako uspoređivanje () i thenCombaring () definitivno složenije scenarije sortiranja učiniti puno čišćim za primjenu.
9. Zaključak
U ovom smo članku vidjeli kako možemo primijeniti sortiranje Polje, Popis, Postavi, i Karta.
Također smo vidjeli kratki uvod o tome kako značajke Java 8 mogu biti korisne u sortiranju poput korištenja Lambda, uspoređivanje () i thenCombaring () i paralelnoSort ().
Svi primjeri korišteni u članku dostupni su na GitHubu.
