Einführung in das Prinzip und den Code der Implementierung des PHP-Schnellsortieralgorithmus

Dieser Artikel stellt Ihnen das Prinzip und den Code des PHP-Schnellsortierungsalgorithmus vor. Ich hoffe, dass er Ihnen als Referenz dienen wird.

Algorithmusprinzip

Die folgenden Animationen stammen aus dem Fünf-Minuten-Algorithmus und demonstrieren die Prinzipien und Schritte des Schnellsortierungsalgorithmus.

Schritte:

• Wählen Sie einen Benchmark-Wert aus dem Array aus.
• Machen Sie das Array größer als der Benchmark-Wert Platzieren Sie diejenigen auf der gleichen Seite und diejenigen, die kleiner als der Benchmark-Wert sind, auf der anderen Seite. Der Benchmark-Wert befindet sich in der mittleren Position
• Rekursiv die Arrays auf beiden Seiten der Spalte sortieren

Code-Implementierung

function quickSort($arr)
{
    $len = count($arr);
    if ($len  $v) {
            $up[] = $arr[$i];
        } else {
            $low[] = $arr[$i];
        }
    }
    $low = quickSort($low);
    $up = quickSort($up);

    return array_merge($low, array($v), $up);
}

Testcode:

$startTime = microtime(1);

$arr = range(1, 10);
shuffle($arr);

echo "before sort: ", implode(', ', $arr), "\n";
$sortArr = quickSort($arr);
echo "after sort: ", implode(', ', $sortArr), "\n";

echo "use time: ", microtime(1) - $startTime, "s\n";

Testergebnis:

before sort: 1, 7, 10, 9, 6, 3, 2, 5, 4, 8
after sort: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
use time: 0.0009009838104248s

Zeitkomplexität

Die Zeitkomplexität der schnellen Sortierung beträgt im schlimmsten Fall (N2) O, die durchschnittliche Zeitkomplexität beträgt O(N*lgN).

Dieser Satz ist leicht zu verstehen: Angenommen, die zu sortierende Reihenfolge enthält N Zahlen. Die zeitliche Komplexität einer Durchquerung beträgt O(N). Wie oft müssen wir sie durchlaufen? Mindestens lg(N+1)-mal und höchstens N-mal.

1) Warum ist es mindestens lg(N+1) mal? Die schnelle Sortierung verwendet zum Durchlaufen die Divide-and-Conquer-Methode. Die Anzahl der Durchläufe ist die Tiefe des Binärbaums ist mindestens lg(N+1). Daher beträgt die Anzahl der Iterationen der Schnellsortierung mindestens das Ig(N+1)-fache.

2) Warum ist es bis zu N-mal? Dies sollte sehr einfach sein. Stellen Sie sich die schnelle Sortierung als einen Binärbaum mit einer maximalen Tiefe von N vor. Daher beträgt die Anzahl der Durchläufe für eine schnelle Lesesortierung höchstens das N-fache.

[Verwandte Empfehlungen: PHP-Video-Tutorial]

Das obige ist der detaillierte Inhalt vonEinführung in das Prinzip und den Code der Implementierung des PHP-Schnellsortieralgorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!