PHP-Codebeispiel zum schnellen Sortieren

Der Inhalt dieses Artikels befasst sich mit dem Codebeispiel für die schnelle Sortierung in PHP. Freunde in Not können darauf verweisen.

Schnellsortierung

Schnellsortierung (Englisch: Quicksort), auch bekannt als Partition-Exchange-Sortierung, kurz für Quick Sort, ein Sortieralgorithmus, der erstmals vorgeschlagen wurde von Tony Hall. Im Durchschnitt erfordert das Sortieren von n Elementen O(n log n) Vergleiche. Im schlimmsten Fall sind O(n2)-Vergleiche erforderlich, dies ist jedoch ungewöhnlich. Tatsächlich ist Quicksort O(n log n) oft deutlich schneller als andere Algorithmen, da seine innere Schleife auf den meisten Architekturen effizient erreicht werden kann.

Die Schritte sind:

Wählen Sie ein Element aus der Sequenz aus, das als „Pivot“ bezeichnet wird.

Ordnen Sie die Sequenz neu an, alle Verhältnisse Elemente mit Elemente mit einem kleineren Basiswert werden vor der Basis platziert und alle Elemente mit einem größeren Basiswert werden nach der Basis platziert (auf beiden Seiten kann die gleiche Anzahl stehen). Nach dieser Partition befindet sich das Datum in der Mitte der Sequenz. Dies wird als Partitionsvorgang bezeichnet.

Sortieren Sie rekursiv das Subarray der Elemente, die kleiner als der Basiswert sind, und das Subarray der Elemente, die größer als der Basiswert sind.

Wenn die Rekursion das Ende erreicht, beträgt die Größe des Arrays Null oder Eins, was bedeutet, dass es sortiert wurde. Dieser Algorithmus wird definitiv enden, da er in jeder Iteration mindestens ein Element an seine endgültige Position verschiebt.

Einführung in Wikipedia. Die Kernidee ist die Verwendung von Rekursion. Die folgende Animation ist sehr anschaulich.

Animationsdemonstration

Beispiel

<?php $arr = [33, 24, 8, 21, 2, 23, 3, 32, 16];

function quickSort($arr)
{
    $count = count($arr);

    if ($count < 2) {
        return $arr;
    }

    $leftArray = $rightArray = array();
    $middle = $arr[0];// 基准值

    for ($i = 1; $i < $count; $i++) {
        // 小于基准值，存入左边；大于基准值，存入右边
        if ($arr[$i] < $middle) {
            $leftArray[] = $arr[$i];
        } else {
            $rightArray[] = $arr[$i];
        }
    }

    $leftArray = quickSort($leftArray);
    $rightArray = quickSort($rightArray);

    return array_merge($leftArray, array($middle), $rightArray);
    // 倒序
    // return array_merge($rightArray, array($middle), $leftArray);
}

print_r(quickSort($arr));
// Array ( [0] => 2 [1] => 3 [2] => 8 [3] => 16 [4] => 21 [5] => 23 [6] => 24 [7] => 32 [8] => 33

Das obige ist der detaillierte Inhalt vonPHP-Codebeispiel zum schnellen Sortieren. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!