So implementieren Sie einen nicht rekursiven Schnellsortierungsalgorithmus in PHP

Einführung

Schnellsortierung ist ein effizienter Sortieralgorithmus, der die Sortierung durch kontinuierliche Aufteilung eines Arrays in zwei Unterarrays erreicht. Beim Quicksort-Algorithmus wird ein Pivot-Wert ausgewählt und alle Elemente, die kleiner als der Pivot-Wert sind, werden auf seiner linken Seite platziert, während alle Elemente, die größer als der Pivot-Wert sind, auf seiner rechten Seite platziert werden. Dieser Prozess wird dann rekursiv auf die linken und rechten Unterarrays angewendet, bis das gesamte Array sortiert ist.

Schnellsortierung ist eine rekursive Funktion, da sie das ursprüngliche Problem in zwei kleinere Unterprobleme zerlegen und dann das ursprüngliche Problem durch rekursives Lösen dieser Unterprobleme lösen muss. Obwohl dieser Ansatz in manchen Situationen effektiv funktionieren kann, weist er einige Einschränkungen auf. Insbesondere bei der Verarbeitung großer Arrays können rekursive Algorithmen den Stapelspeicher des Computers erschöpfen und eine Stapelüberlaufausnahme verursachen. Darüber hinaus kann der zusätzliche Overhead rekursiver Funktionsaufrufe auch zu Leistungseinbußen des Algorithmus führen.

Daher kann es in manchen Fällen sinnvoller sein, nicht-rekursive Implementierungsmethoden zu verwenden. In diesem Artikel stellen wir einen nicht rekursiven Algorithmus zur schnellen Sortierung mit PHP vor.

Algorithmusimplementierung

Wir definieren zunächst eine Hilfsfunktionspartition, die verwendet wird, um ein Array in zwei Unterarrays zu unterteilen: eines, das alle Elemente enthält, die kleiner als der Basiswert sind, und eines, das alle Elemente enthält, die größer als der Basiswert sind.

function partition(&$arr, $left, $right) {
    $pivot = $arr[$right]; // 选择最后一个元素作为基准值
    $i = $left - 1;
    for ($j = $left; $j < $right; $j++) {
        if ($arr[$j] < $pivot) {
            $i++;
            list($arr[$i], $arr[$j]) = array($arr[$j], $arr[$i]); // 交换i和j处的元素
        }
    }
    list($arr[$i + 1], $arr[$right]) = array($arr[$right], $arr[$i + 1]); // 将基准值放到正确的位置
    return $i + 1;
}

Diese Funktion wählt das letzte Element aus dem Array als Basiswert aus und platziert alle Elemente, die kleiner als der Basiswert sind, auf der linken Seite des Arrays, indem sie die Array-Elemente vertauscht. In diesem Prozess verwenden wir die Variable $i, um den Index des aktuell verarbeiteten Subarrays aufzuzeichnen, und $j wird verwendet, um das gesamte Array zu durchlaufen. Wenn wir ein Element finden, das kleiner als der Pivotwert ist, verschieben wir $i um eine Position nach rechts und platzieren das Element an der Position von $i. Schließlich platzieren wir den Basiswert an der Endposition $i + 1.

Mit der Partitionsfunktion können wir jetzt eine nicht rekursive Version des Quicksort-Algorithmus implementieren. In dieser Version verwenden wir einen Stapel, um die zu verarbeitenden Subarrays zu speichern. Wenn wir ein Subarray verarbeiten, zeichnen wir zunächst die linke und rechte Grenze des Subarrays auf dem Stapel auf und teilen es dann weiter in zwei kleinere Subarrays auf, bis alle Subarrays sortiert sind.

function quick_sort(&$arr) {
    $stack = new SplStack(); // 使用SplStack实现栈
    $stack->push(count($arr) - 1); // 将整个数组的下标压入栈
    $stack->push(0);
    while (!$stack->isEmpty()) {
        $left = $stack->pop();
        $right = $stack->pop();
        $pivotIndex = partition($arr, $left, $right);
        if ($left < $pivotIndex - 1) {
            $stack->push($pivotIndex - 1);
            $stack->push($left);
        }
        if ($pivotIndex + 1 < $right) {
            $stack->push($right);
            $stack->push($pivotIndex + 1);
        }
    }
}

In dieser Version des Codes verwenden wir die SplStack-Klasse, um den Stack zu implementieren. Wir verschieben zunächst die linken und rechten Grenzen des gesamten Arrays auf den Stapel, entfernen dann kontinuierlich die linken und rechten Grenzen vom Stapel und übergeben sie an die Partitionsfunktion, um das Unterarray zu unterteilen. Wenn left < PivotIndex - 1, bedeutet dies, dass das linke Subarray noch nicht sortiert ist und auf den Stapel verschoben wird, um auf die Verarbeitung zu warten. Wenn PivotIndex + 1 < rechts ist, bedeutet dies, dass das rechte Subarray noch nicht sortiert ist und zur Verarbeitung auf den Stapel verschoben wird.

Die zeitliche Komplexität dieses Algorithmus beträgt O(nlogn). Obwohl es nicht in allen Fällen so schnell ist wie die rekursive Version der Schnellsortierung, kann es die räumliche Komplexität des Algorithmus erheblich reduzieren und den Overhead rekursiver Funktionsaufrufe vermeiden. Wenn Sie schnell ein großes Array in PHP sortieren müssen, ist dieser Algorithmus möglicherweise besser für Ihre Anforderungen geeignet als die rekursive Version von Quicksort.

Das obige ist der detaillierte Inhalt vonSo implementieren Sie einen nicht rekursiven Schnellsortierungsalgorithmus in PHP. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!