Implementierung der PHP-Schnellsortierung

Schnellsortierung ist ein gängiger Sortieralgorithmus und läuft in den meisten Fällen schneller als andere Sortieralgorithmen, insbesondere bei Sortierszenarien großer Datenmengen. Auch die Implementierung der Schnellsortierung in PHP ist sehr einfach und erfordert nur wenige Codezeilen. In diesem Artikel wird die Implementierung der schnellen Sortierung in PHP vorgestellt.

Was ist Schnellsortierung? Schnellsortierung ist ein Sortieralgorithmus, der auf „Teile und herrsche“ basiert und die zu sortierende Sequenz in mehrere Teilsequenzen aufteilt und jede Teilsequenz nach einem Benchmarkwert sortiert. Der Basiswert kann eine beliebige Zahl sein, normalerweise wird das erste oder letzte Element genommen und dann werden die Daten in zwei Gruppen unterteilt, wobei eine Seite größer als der Basiswert und die andere Seite kleiner als der Basiswert ist. Durch rekursiven Aufruf dieses Prozesses und abschließendes Zusammenführen der Teilsequenzen kann eine geordnete Sequenz erhalten werden.

PHP-Schnellsortierungsimplementierung

Der Code lautet wie folgt:

function quickSort($arr)
{
    $length = count($arr);
    if ($length <= 1) {
        return $arr;
    }
    $left = $right = array();
    $pivot = $arr[0];
    for ($i = 1; $i < $length; $i++) {
        if ($arr[$i] < $pivot) {
            $left[] = $arr[$i];
        } else {
            $right[] = $arr[$i];
        }
    }
    return array_merge(quickSort($left), array($pivot), quickSort($right));
}

Im obigen Code ist $arr das zu sortierende Array, $left- und $right-Arrays werden zum Speichern von Zahlen verwendet, die kleiner bzw. größer als der Benchmark-Wert sind , $pivot Als Basiswert werden die Zahlen im Array durch eine Schleife entsprechend ihrer Größe in zwei Kategorien unterteilt und schließlich die Zahlen im linken und rechten Teil kombiniert.

Die zeitliche Komplexität der schnellen Sortierung beträgt O (nlogn) und ist auch in der tatsächlichen Verwendung sehr effizient.

Zusammenfassung

Schnellsortierung ist ein gängiger Sortieralgorithmus, der auf Teilen und Erobern basiert. Durch Auswahl einer Benchmark-Nummer wird das zu sortierende Array in zwei Teilsequenzen unterteilt, die Teilsequenzen werden rekursiv sortiert und die beiden Teilsequenzen werden schließlich zu einer zusammengeführt geordnete Reihenfolge. Es ist auch sehr einfach, die Schnellsortierung in PHP zu implementieren. Der oben angegebene Code dient als Referenz. Die Zeitkomplexität des Schnellsortierungsalgorithmus beträgt O(nlogn) und er funktioniert im tatsächlichen Gebrauch gut.

Das obige ist der detaillierte Inhalt vonImplementierung der PHP-Schnellsortierung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!