Implementieren Sie eine funktionsähnliche schnelle Sortierung in Java

Einführung

Ich habe versucht, eine schnelle Sortierung mit Lambda-Ausdruck und Stream in Java zu implementieren. Die Zielgruppe für diesen Artikel ist:

• Leute, die Scala gemeistert haben
• Personen, die mit den Funktionsfunktionen von Java beginnen möchten

Lambda-Ausdruck

Der Lambda-Ausdruck kann in der Form (Argument) -> Rückgabewert geschrieben werden, und die Funktion kann mit der Methode apply aufgerufen werden.

import java.util.function.Function;

public class Main {
    public static void main(String[] args) {
        Function<String, String> addHoge = (final String str) -> str + "hoge";
        System.out.println(addHoge.apply("fuga"));
    }
}

Wenn Sie mehrere Ausdrücke schreiben möchten, können Sie auch Blöcke verwenden.

import java.util.function.Function;

public class Main {
    public static void main(String[] args) {
        Function<String, String> addHoge = (final String str) -> {
            String hoge = "hoge";
            return str + hoge;
        };
        System.out.println(addHoge.apply("fuga"));
    }
}

Stream Stream ist eine Klasse, die Operationen vom Funktionstyp für die Elemente einer Sammlung unterstützt. Stream kann durch Aufrufen der Methode "stream ()" der Auflistungsklasse verwendet werden.

Wenn Sie ein Programm schreiben, das mit stream () ein Vielfaches von 2 anzeigt, ist dies wie folgt.

Java

Arrays.asList(3, 21, 34, 0).stream().filter(n -> n % 2 == 0).forEach(System.out::println);

Mit Scala sieht es so aus: Im Vergleich zu Java ist der Code einfacher, da Sie nicht "stream ()" schreiben müssen.

Scala

List(3, 21,34, 0).filter(_ % 2 == 0).foreach(println)

Quellcode (Scala)

Bevor Sie die schnelle Sortierung in Java implementieren, finden Sie hier den in Scala implementierten Code. Die schnelle Sortierung "Pivot" wird am Anfang des Arrays angegeben.

object Main extends App {
    println(quickSort(List(3, 21, 34, 0, -30, 55, 10)))
    
    def quickSort(nums: List[Int]): List[Int] = {
      nums.headOption.fold(List[Int]()){ pivot =>
        val left = nums.filter(_ < pivot)
        val right = nums.filter(pivot < _)
        quickSort(left) ++ List(pivot) ++ quickSort(right)
      }
    }
}

Quellcode (Java)

Das Folgende ist eine Implementierung der schnellen Sortierung in Java.

Im Vergleich zu Scalas Code bin ich von der Menge an Java-Code überwältigt, aber ich denke, die Logik selbst hat fast die gleiche Implementierung.

Der einzige Unterschied in der Logik ist die Fold-Methode. Es gibt Stellen, an denen die Falzmethode im Scala-Code verwendet wird, aber die Falzmethode ist im optionalen Java-Typ (Optionstyp in Scala) nicht vorhanden. Stattdessen werden die Map-Methode und die OrElseGet-Methode (getOrElse-Methode in Scala) in Kombination verwendet.

import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.List;
import static java.util.stream.Collectors.toList;
import java.util.stream.Stream;

public class Main {
    public static void main(String[] args) {
        final List<Integer> nums = Arrays.asList(3, 21, 34, 0, -30, 55, 10);
        final List<Integer> sorted = quickSort(nums);
        System.out.println(sorted.toString());
    }

    private static List<Integer> quickSort(final List<Integer> nums) {
        return nums.stream().findFirst().map((final Integer pivot) -> {
            final List<Integer> left = nums.stream().filter(n -> n < pivot).collect(toList());
            final List<Integer> middle = Collections.singletonList(pivot);
            final List<Integer> right = nums.stream().filter(n -> pivot < n).collect(toList());
            return Stream.of(quickSort(left), middle, quickSort(right)).flatMap(Collection::stream).collect(toList());
        }).orElseGet(Collections::emptyList);
    }
}