Sortieren in Java

1. Übersicht

In diesem Artikel wird erläutert, wie Sie die Sortierung auf Array , List , Set und Map in Java 7 und Java 8 anwenden .

2. Sortieren mit Array

Beginnen wir damit, zuerst ganzzahlige Arrays mit der Methode Arrays.sort () zu sortieren .

Wir definieren die folgenden int- Arrays in einer @ Before jUnit-Methode:

@Before public 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. Komplettes Array sortieren

Verwenden wir jetzt die einfache Array.sort () -API :

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

Das unsortierte Array ist jetzt vollständig sortiert:

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

Wie in der offiziellen JavaDoc erwähnt, Arrays.sort verwendet Dual-Pivot Quicksort auf Primitiven . Es bietet O (n log (n)) -Leistung und ist in der Regel schneller als herkömmliche Quicksort-Implementierungen (mit einem Pivot). Es wird jedoch eine stabile, adaptive, iterative Implementierung des Mergesort-Algorithmus für Array of Objects verwendet.

2.2. Teil eines Arrays sortieren

Arrays.sort hat eine weitere Art APIs - was wir hier besprechen werden:

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

Dadurch wird nur ein Teil des Arrays zwischen den beiden Indizes sortiert.

Schauen wir uns ein kurzes Beispiel an:

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

Die Sortierung wird nur für folgende Sub-Array-Elemente durchgeführt ( toIndex wäre exklusiv):

[255, 7, 88, 200]

Das resultierende sortierte Unterarray einschließlich des Hauptarrays wäre:

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

2.3. Java 8 Arrays.sort vs Arrays.parallelSort

Java 8 enthält eine neue API - parallelSort - mit einer ähnlichen Signatur wie die Arrays.sort () - API:

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

Hinter den Kulissen von parallelSort () wird das Array in verschiedene Unterarrays unterteilt (gemäß der Granularität im Algorithmus von parallelSort ). Jedes Sub-Array wird mit Arrays.sort () in verschiedenen Threads sortiert, sodass die Sortierung parallel ausgeführt und schließlich als sortiertes Array zusammengeführt werden kann.

Beachten Sie, dass der gemeinsame ForJoin-Pool zum Ausführen dieser parallelen Aufgaben und zum anschließenden Zusammenführen der Ergebnisse verwendet wird.

Das Ergebnis von Arrays.parallelSort wird natürlich das gleiche sein wie Array.sort . Es geht nur darum, Multithreading zu nutzen.

Schließlich gibt es auch in Arrays.parallelSort ähnliche Varianten von API Arrays.sort :

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

3. Eine Liste sortieren

Verwenden wir nun die API Collections.sort () in java.utils.Collections , um eine Liste von Ganzzahlen zu sortieren :

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

Die Liste vor dem Sortieren enthält die folgenden Elemente:

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

Und natürlich nach dem Sortieren:

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

Wie in Oracle JavaDoc für Collections.Sort erwähnt , verwendet es einen modifizierten Mergesort und bietet eine garantierte Leistung von n log (n) .

4. Sortieren eines Sets

Als nächstes verwenden wir Collections.sort () , um ein LinkedHashSet zu sortieren .

Wir verwenden das LinkedHashSet, da es die Einfügereihenfolge beibehält.

Beachten Sie, wie, um die zu verwenden Art API in Sammlungen - wir sind erste Verpackungs das Gerät in einer Liste :

@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})); List list = new ArrayList(integersSet); Collections.sort(Comparator.reverseOrder()); integersSet = new LinkedHashSet(list); assertTrue(Arrays.equals( integersSet.toArray(), descSortedIntegersSet.toArray())); }

Die Comparator.reverseOrder () -Methode kehrt die durch die natürliche Reihenfolge auferlegte Reihenfolge um.

5. Karte sortieren

In diesem Abschnitt werden wir uns mit dem Sortieren einer Karte befassen - sowohl nach Schlüsseln als auch nach Werten.

Definieren wir zunächst die Karte, die sortiert werden soll:

@Before public void initVariables () { .... HashMap map = new 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. Sorting Karte von Keys

We'll now extract keys and values entries from the HashMap and sort it based on the values of the keys in this example:

@Test public void givenMap_whenSortingByKeys_thenSortedMap() { Integer[] sortedKeys = new Integer[] { 6, 12, 22, 55, 66, 77 }; List
    
      entries = new ArrayList(map.entrySet()); Collections.sort(entries, new 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)); }
     
    

Note how we used the LinkedHashMap while copying the sorted Entries based on keys (because HashSet doesn't guarantee the order of keys).

The Map before sorting :

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

The Map after sorting by keys:

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

5.2. Sorting Map by Values

Here we will be comparing values of HashMap entries for sorting based on values of HashMap:

@Test public void givenMap_whenSortingByValues_thenSortedMap() { String[] sortedValues = new String[] { "Apple", "Earl", "George", "John", "Pearl", "Rocky" }; List
    
      entries = new ArrayList(map.entrySet()); Collections.sort(entries, new 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)); }
     
    

The Map before sorting:

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

The Map after sorting by values:

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

6. Sorting Custom Objects

Let's now work with a custom object:

public class Employee implements Comparable { private String name; private int age; private double salary; public Employee(String name, int age, double salary) { ... } // standard getters, setters and toString }

We'll be using the following Employee Array for sorting example in the following sections:

@Before public void initVariables () { .... employees = new Employee[] { new Employee("John", 23, 5000), new Employee("Steve", 26, 6000), new Employee("Frank", 33, 7000), new Employee("Earl", 43, 10000), new Employee("Jessica", 23, 4000), new Employee("Pearl", 33, 6000)}; employeesSorted = new Employee[] { new Employee("Earl", 43, 10000), new Employee("Frank", 33, 70000), new Employee("Jessica", 23, 4000), new Employee("John", 23, 5000), new Employee("Pearl", 33, 4000), new Employee("Steve", 26, 6000)}; employeesSortedByAge = new Employee[] { new Employee("John", 23, 5000), new Employee("Jessica", 23, 4000), new Employee("Steve", 26, 6000), new Employee("Frank", 33, 70000), new Employee("Pearl", 33, 4000), new Employee("Earl", 43, 10000)}; }

We can sort arrays or collections of custom objects either:

  1. in the natural order (Using the Comparable Interface) or
  2. in the order provided by a ComparatorInterface

6.1. Using Comparable

The natural order in java means an order in which primitive or Object should be orderly sorted in a given array or collection.

Both java.util.Arrays and java.util.Collections have a sort() method, and It's highly recommended that natural orders should be consistent with the semantics of equals.

In this example, we will consider employees with the same name as equal:

@Test public void givenEmpArray_SortEmpArray_thenSortedArrayinNaturalOrder() { Arrays.sort(employees); assertTrue(Arrays.equals(employees, employeesSorted)); }

You can define the natural order for elements by implementing a Comparable interface which has compareTo() method for comparing current object and object passed as an argument.

To understand this clearly, let's see an example Employee class which implements Comparable Interface:

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; return getName().compareTo(e.getName()); } }

Generally, the logic for comparison will be written the method compareTo. Here we are comparing the employee order or name of the employee field. Two employees will be equal if they have the same name.

Now when Arrays.sort(employees); is called in the above code, we now know what is the logic and order which goes in sorting the employees as per the age :

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

We can see the array is sorted by name of the employee – which now becomes a natural order for Employee Class.

6.2. Using Comparator

Now, let's sort the elements using a Comparator interface implementation – where we pass the anonymous inner class on-the-fly to the Arrays.sort() API:

@Test public void givenIntegerArray_whenUsingSort_thenSortedArray() { Integer [] integers = ArrayUtils.toObject(toSort); Arrays.sort(integers, new Comparator() { @Override public int compare(Integer a, Integer b) { return Integer.compare(a, b); } }); assertTrue(Arrays.equals(integers, ArrayUtils.toObject(sortedInts))); }

Now lets sort employees based on salary – and pass in another comparator implementation:

Arrays.sort(employees, new Comparator() { @Override public int compare(Employee o1, Employee o2) { return Double.compare(o1.getSalary(), o2.getSalary()); } });

The sorted Employees arrays based on salary will be:

[(Jessica,23,4000.0), (John,23,5000.0), (Pearl,33,6000.0), (Steve,26,6000.0), (Frank,33,7000.0), (Earl,43,10000.0)] 

Note that we can use Collections.sort() in a similar fashion to sort List and Set of Objects in Natural or Custom order as described above for Arrays.

7. Sorting With Lambdas

Start with Java 8, we can use Lambdas to implement the Comparator Functional Interface.

You can have a look at the Lambdas in Java 8 writeup to brush up on the syntax.

Let's replace the old comparator:

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

With the equivalent implementation, using Lambda expression:

Comparator c = (a, b) -> Integer.compare(a, b);

Finally, let's write the 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(sortedInts))); }

As you can see, a much cleaner and more concise logic here.

8. Using Comparator.comparing and Comparator.thenComparing

Java 8 comes with two new APIs useful for sorting – comparing() and thenComparing() in the Comparator interface.

These are quite handy for the chaining of multiple conditions of the Comparator.

Let's consider a scenario where we may want to compare Employee by age and then by name:

@Test public void givenArrayObjects_whenUsingComparing_thenSortedArrayObjects() { List employeesList = Arrays.asList(employees); employees.sort(Comparator.comparing(Employee::getAge)); assertTrue(Arrays.toString(employees.toArray()) .equals(sortedArrayString)); }

In this example, Employee::getAge is the sorting key for Comparator interface implementing a functional interface with compare function.

Here's the array of Employees after sorting:

[(John,23,5000.0), (Jessica,23,4000.0), (Steve,26,6000.0), (Frank,33,7000.0), (Pearl,33,6000.0), (Earl,43,10000.0)]

Here the employees are sorted based on age.

We can see John and Jessica are of same age – which means that the order logic should now take their names into account- which we can achieve with thenComparing():

... employees.sort(Comparator.comparing(Employee::getAge) .thenComparing(Employee::getName)); ... 

After sorting with above code snippet, the elements in employee array would be sorted as:

[(Jessica,23,4000.0), (John,23,5000.0), (Steve,26,6000.0), (Frank,33,7000.0), (Pearl,33,6000.0), (Earl,43,10000.0) ]

Thus comparing() and thenComparing() definitely make more complex sorting scenarios a lot cleaner to implement.

9. Conclusion

In this article, we saw how we can apply sorting to Array, List, Set, and Map.

Wir haben auch eine kurze Einführung darüber gesehen, wie Funktionen von Java 8 beim Sortieren wie der Verwendung von Lambdas, Vergleichen () und dann Vergleichen () und parallelSort () nützlich sein können .

Alle im Artikel verwendeten Beispiele sind auf GitHub verfügbar.