PHP-Array-Schnellsortierung vs. Zusammenführungssortierung

Schnellsortierung ist ein rekursiver Algorithmus, der das Array in kleinere und größere Elemente aufteilt und diese rekursiv sortiert, während die Zusammenführungssortierung das Array rekursiv in kleinere Arrays aufteilt, jedes kleine Array sortiert und es dann wieder mit dem ursprünglichen Array zusammenführt. Die von PHP implementierten Codes sind: Schnelle Sortierung: Teilen Sie das Array in Elemente auf, die kleiner und größer als der Basiswert sind, und sortieren Sie dann jeden Teil rekursiv. Zusammenführungssortierung: Teilen Sie ein Array rekursiv in kleinere Arrays auf, sortieren Sie jedes kleinere Array und führen Sie dann die sortierten kleineren Arrays wieder mit dem ursprünglichen Array zusammen.

PHP-Array-Schnellsortierung vs. Zusammenführungssortierung

Was sind Schnellsortierung und Zusammenführungssortierung?

Schnellsortierung und Zusammenführungssortierung sind beide gängige Algorithmen zum Sortieren von Arrays.

• Schnellsortierung: Teilen Sie das Array in zwei Teile, von denen einer kleinere Elemente und der andere größere Elemente enthält, und sortieren Sie dann jeden Teil rekursiv.
• Sortierung zusammenführen: Rekursives Teilen des Arrays in kleinere Arrays, Sortieren jedes kleineren Arrays und Zusammenführen der sortierten kleineren Arrays wieder in das ursprüngliche Array.

Code-Implementierung 是 Das Folgende ist eine schnelle Entladungs- und Zusammenführungssortierungsfunktion, die mit PHP implementiert wurde:

Schnelle Eliminierung:

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

E

Zusammenführungssortierung:

function mergeSort($arr) {
    $length = count($arr);
    if ($length <= 1) {
        return $arr;
    }
    $mid = floor($length / 2);
    $left = array_slice($arr, 0, $mid);
    $right = array_slice($arr, $mid);
    return merge(mergeSort($left), mergeSort($right));
}

function merge($left, $right) {
    $result = [];
    $lIndex = $rIndex = 0;
    while ($lIndex < count($left) && $rIndex < count($right)) {
        if ($left[$lIndex] < $right[$rIndex]) {
            $result[] = $left[$lIndex++];
        } else {
            $result[] = $right[$rIndex++];
        }
    }
    while ($lIndex < count($left)) {
        $result[] = $left[$lIndex++];
    }
    while ($rIndex < count($right)) {
        $result[] = $right[$rIndex++];
    }
    return $result;
}

tatsächlicher Kampffall

Unter Berücksichtigung einer Unordnung ungeordnetes Array von ganzen Zahlen .

Quicksort verwenden:

$sortedArray = quickSort([5, 2, 8, 3, 1, 9, 4, 7, 6]);
print_r($sortedArray);

[5, 2, 8, 3, 1, 9, 4, 7, 6]Ausgabe:

[1, 2, 3, 4, 5, 6, 7, 8, 9]

Zusammenführungssortierung verwenden:

$sortedArray = mergeSort([5, 2, 8, 3, 1, 9, 4, 7, 6]);
print_r($sortedArray);

Ausgabe:

[1, 2, 3, 4, 5, 6, 7, 8, 9]

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