Komplexitätsanalyse verschiedener PHP-Array-Sortieralgorithmen

PHP-Array-Sortieralgorithmus-Komplexität: Blasensortierung: O(n^2) Schnelle Sortierung: O(n log n) (Durchschnitt) Zusammenführungssortierung: O(n log n)

PHP-Array-Sortieralgorithmus-Komplexitätsanalyse

In PHP gibt es verschiedene Sortieralgorithmen, mit denen Elemente in einem Array sortiert werden können. Die Effizienz jedes Algorithmus variiert je nach Größe des Arrays und der Verteilung der Daten.

Bubble Sort

Bubble Sort ist ein einfacher Sortieralgorithmus, der jedoch weniger effizient ist. Dabei werden benachbarte Elemente wiederholt verglichen und das größere Element am Ende des Arrays ausgetauscht.

function bubbleSort($arr) {
    for ($i = 0; $i < count($arr); $i++) {
        for ($j = 0; $j < count($arr) - $i - 1; $j++) {
            if ($arr[$j] > $arr[$j + 1]) {
                $temp = $arr[$j];
                $arr[$j] = $arr[$j + 1];
                $arr[$j + 1] = $temp;
            }
        }
    }
    return $arr;
}

Zeitkomplexität: O(n^2)

Schnelle Sortierung

Schnelle Sortierung ist ein Divide-and-Conquer-Algorithmus und gilt allgemein als der effizienteste Sortieralgorithmus. Es verwendet Rekursion, um das Array in kleinere Unterarrays zu unterteilen und jedes Unterarray zu sortieren.

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

Zeitliche Komplexität: O(n log n) (im Durchschnitt)

Merge-Sortierung

Merge-Sortierung ist ebenfalls ein Divide-and-Conquer-Algorithmus. Es funktioniert, indem es das Array rekursiv in kleinere Unterarrays aufteilt, die Unterarrays sortiert und dann die sortierten Unterarrays zusammenführt.

function mergeSort($arr) {
    if (count($arr) <= 1) {
        return $arr;
    }
    $mid = count($arr) / 2;
    $left = mergeSort(array_slice($arr, 0, $mid));
    $right = mergeSort(array_slice($arr, $mid));
    return merge($left, $right);
}
function merge($left, $right) {
    $merged = [];
    $i = $j = 0;
    while ($i < count($left) && $j < count($right)) {
        if ($left[$i] <= $right[$j]) {
            $merged[] = $left[$i];
            $i++;
        } else {
            $merged[] = $right[$j];
            $j++;
        }
    }
    return array_merge($merged, array_slice($left, $i), array_slice($right, $j));
}

Zeitkomplexität: O(n log n)

Praktischer Fall

Angenommen, Sie haben ein Array mit 10000 ganzen Zahlen. Sie können dieses Array mit dem obigen Algorithmus sortieren und mit der PHP-Funktion microtime() messen, wie lange das Sortieren dauert.

$arr = range(1, 10000);
shuffle($arr); // 打乱数组以获得更现实的结果

$timeStart = microtime(true);
bubbleSort($arr);
$timeEnd = microtime(true);
echo "Bubble Sort: " . ($timeEnd - $timeStart) . " 秒\n";

$timeStart = microtime(true);
quickSort($arr);
$timeEnd = microtime(true);
echo "Quick Sort: " . ($timeEnd - $timeStart) . " 秒\n";

$timeStart = microtime(true);
mergeSort($arr);
$timeEnd = microtime(true);
echo "Merge Sort: " . ($timeEnd - $timeStart) . " 秒\n";

Für ein Array von 10.000 Ganzzahlen lauten die Ergebnisse wie folgt:

Bubble Sort: 1.0129920272827 秒
Quick Sort: 0.001443982124329 秒
Merge Sort: 0.001151084899902 秒

Die Ergebnisse zeigen, dass die schnelle Sortierung und die Zusammenführungssortierung deutlich effizienter sind als die Blasensortierung.

Das obige ist der detaillierte Inhalt vonKomplexitätsanalyse verschiedener PHP-Array-Sortieralgorithmen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!