So implementieren Sie eine schnelle Sortierung in PHP

So implementieren Sie die schnelle Sortierung in PHP: Erstellen Sie zuerst eine PHP-Beispieldatei. Erstellen Sie dann die Austauschfunktion und die Hauptfunktion. Sortieren Sie dann die untere und obere Untertabelle rekursiv.

Empfohlen: „PHP-Video-Tutorial“

Grundidee:

Quicksort ist eine Verbesserung der Blasensortierung. Seine Grundidee besteht darin, die zu sortierenden Datensätze durch eine Sortierung in zwei unabhängige Teile zu unterteilen. Die Schlüsselwörter eines Teils sind kleiner als die Schlüsselwörter des anderen Teils des Datensatzes. Dann können die beiden Teile der Datensätze schnell getrennt sortiert werden. Der gesamte Sortiervorgang kann rekursiv ausgeführt werden, um den Zweck der Reihenfolge der gesamten Reihenfolge zu erreichen.

Grundlegende Algorithmusschritte:

Zum Beispiel:

Angenommen, der Datensatz, der jetzt sortiert werden soll, lautet:

6   2   7   3   8   9

Der erste Schritt besteht darin, eine Variable zu erstellen, die $low auf den ersten Datensatz im Datensatz zeigt und $high auf Im letzten Datensatz wird $pivot als Pivot dem ersten Element des zu sortierenden Datensatzes (nicht unbedingt dem ersten) zugewiesen, hier:

$low = 0;
$high = 5;
$pivot = 6;

Im zweiten Schritt müssen wir alle Zahlen, die kleiner als $pivot sind, in den verschieben links von $pivot , sodass wir beginnen können, nach einer Zahl kleiner als 6 zu suchen, beginnend bei $high, von rechts nach links schauend und den Wert der Variablen $high ständig verringernd. Wir finden die ersten Daten mit dem Index 3, die kleiner sind als 6, also verschieben wir die Daten 3 an die Position von Index 0 (die Position, auf die $low zeigt), verschieben die Daten 6 von Index 0 nach Index 3 und schließen den ersten Vergleich ab:

3   2   7   6   8   9

//这时候,$high 减小为 3
$low = 0;
$high = 3;
$pivot = 6;

Der dritte Schritt, Wir beginnen mit dem zweiten Vergleich. Dieses Mal müssen Sie nach etwas suchen, das größer als $pivot ist, und zwar von vorne bis hinten. Erhöhen Sie die Variable $low und stellen Sie fest, dass die Daten bei Index 2 die ersten sind, die größer als $pivot sind. Daher verwenden wir die Daten 7 bei Index 2 (die Position, auf die durch $low gezeigt wird) und die Daten 7 bei Index 3 (die Position, auf die gezeigt wird). at by $high). 6 der Daten werden ausgetauscht und der Datenstatus wird zur folgenden Tabelle:

3   2   6   7   8   9

//这时候,$high 减小为 3
$low = 2;
$high = 3;
$pivot = 6;

Der Abschluss des zweiten und dritten Schritts wird als Abschluss eines Zyklus bezeichnet.

Der vierte Schritt (d. h. der Beginn des nächsten Zyklus) ahmt den Prozess des zweiten Schritts nach.
Der fünfte Schritt besteht darin, den Prozess des dritten Schritts nachzuahmen.

Nach dem Ausführen der zweiten Schleife ist der Datenstatus wie folgt:

3   2   6   7   8   9

//这时候,$high 减小为 3
$low = 2;
$high = 2;
$pivot = 6;

In diesem Schritt stellen wir fest, dass $low und $high „zusammentreffen“: Sie zeigen beide auf Index 2. Damit ist der erste Vergleich beendet. Das Ergebnis ist wie folgt: Alle Zahlen links von $pivot(=6) sind kleiner als dieser Wert und alle Zahlen rechts von $pivot sind größer als dieser Wert.

Dann gruppieren Sie die Daten {3, 2} und {7, 8, 9} auf beiden Seiten von $pivot und führen Sie den obigen Vorgang aus, bis keine Gruppierung mehr möglich ist.

Hinweis: Der erste Durchgang der Schnellsortierung liefert nicht direkt das Endergebnis, sondern teilt nur die Zahlen größer als k und kleiner als k auf beide Seiten von k auf. Um das Endergebnis zu erhalten, müssen Sie diesen Schritt erneut für die Arrays auf beiden Seiten von Index 2 ausführen und dann das Array zerlegen, bis das Array nicht mehr zerlegt werden kann (nur ein Datenwert), um das richtige Ergebnis zu erhalten.

Algorithmusimplementierung:

//交换函数
function swap(array &$arr,$a,$b){
    $temp = $arr[$a];
    $arr[$a] = $arr[$b];
    $arr[$b] = $temp;
}

//主函数：
function QuickSort(array &$arr){
    $low = 0;
    $high = count($arr) - 1;
    QSort($arr,$low,$high);
}

Da in der Hauptfunktion beim ersten Durchgang der Schnellsortierung das gesamte Array sortiert wird, ist der Startpunkt $low=0,$high=count($arr)-1.
Dann ist die Funktion QSort() ein rekursiver Aufrufprozess, also ist sie gekapselt:

function QSort(array &$arr,$low,$high){
    //当 $low >= $high 时表示不能再进行分组，已经能够得出正确结果了
    if($low < $high){
        $pivot = Partition($arr,$low,$high);  //将$arr[$low...$high]一分为二，算出枢轴值
        QSort($arr,$low,$pivot - 1);	//对低子表（$pivot左边的记录）进行递归排序
        QSort($arr,$pivot + 1,$high);	//对高子表（$pivot右边的记录）进行递归排序
    }
}

Anhand der Funktion QSort() oben können wir erkennen, dass die Funktion Partition() aufgrund der Funktionen der Kern des gesamten Codes ist dieser Funktion Ja: Wählen Sie eines der Schlüsselwörter aus, beispielsweise das erste Schlüsselwort. Dann versuchen wir unser Bestes, es an einer bestimmten Position zu platzieren, sodass die Werte auf der linken Seite kleiner und die Werte auf der rechten Seite größer sind. Wir nennen ein solches Schlüsselwort einen Pivot.

Gehe direkt zum Code:

//选取数组当中的一个关键字，使得它处于数组某个位置时，左边的值比它小，右边的值比它大，该关键字叫做枢轴
//使枢轴记录到位，并返回其所在位置
function Partition(array &$arr,$low,$high){
    $pivot = $arr[$low];   //选取子数组第一个元素作为枢轴
    while($low < $high){  //从数组的两端交替向中间扫描（当 $low 和 $high 碰头时结束循环）
        while($low < $high && $arr[$high] >= $pivot){
            $high --;
        }
        swap($arr,$low,$high);	//终于遇到一个比$pivot小的数，将其放到数组低端

        while($low < $high && $arr[$low] <= $pivot){
            $low ++;
        }
        swap($arr,$low,$high);	//终于遇到一个比$pivot大的数，将其放到数组高端
    }
    return $low;   //返回high也行，毕竟最后low和high都是停留在pivot下标处
}

Der gesamte kombinierte Code lautet wie folgt:

function swap(array &$arr,$a,$b){
    $temp = $arr[$a];
    $arr[$a] = $arr[$b];
    $arr[$b] = $temp;
}

function Partition(array &$arr,$low,$high){
    $pivot = $arr[$low];   //选取子数组第一个元素作为枢轴
    while($low < $high){  //从数组的两端交替向中间扫描
        while($low < $high && $arr[$high] >= $pivot){
            $high --;
        }
        swap($arr,$low,$high);	//终于遇到一个比$pivot小的数，将其放到数组低端
        while($low < $high && $arr[$low] <= $pivot){
            $low ++;
        }
        swap($arr,$low,$high);	//终于遇到一个比$pivot大的数，将其放到数组高端
    }
    return $low;   //返回high也行，毕竟最后low和high都是停留在pivot下标处
}

function QSort(array &$arr,$low,$high){
    if($low < $high){
        $pivot = Partition($arr,$low,$high);  //将$arr[$low...$high]一分为二，算出枢轴值
        QSort($arr,$low,$pivot - 1);   //对低子表进行递归排序
        QSort($arr,$pivot + 1,$high);  //对高子表进行递归排序
    }
}

function QuickSort(array &$arr){
    $low = 0;
    $high = count($arr) - 1;
    QSort($arr,$low,$high);
}

Wir nennen den Algorithmus:

$arr = array(9,1,5,8,3,7,4,6,2);
QuickSort($arr);
var_dump($arr);

Komplexitätsanalyse:

In der optimalen Situation, das heißt, wenn die Achse so ausgewählt ist Beim Mittelwert des gesamten Arrays wird das Array jedes Mal in zwei Hälften geteilt. Daher beträgt die Zeitkomplexität im optimalen Fall O(nlogn) (wie Heap-Sortierung und Zusammenführungssortierung).

Im schlimmsten Fall, wenn die zu sortierende Reihenfolge in Vorwärts- oder Rückwärtsreihenfolge erfolgt, können bei der Auswahl des Pivots nur Kantendaten ausgewählt werden. Jede Unterteilung führt zu einem Datensatz weniger als die vorherige Unterteilung, die andere Unterteilung jedoch leer sein. Die endgültige Zeitkomplexität einer solchen Situation beträgt O(n^2).

Basierend auf den besten und schlechtesten Fällen beträgt die durchschnittliche Zeitkomplexität O(nlogn).

Schnellsortierung ist eine instabile Sortiermethode.

Weil die schnelle Sortierung eine relativ fortgeschrittene Sortierung ist und als einer der zehn besten Algorithmen des 20. Jahrhunderts aufgeführt wird. . . . Warum sollten wir bei solch einem großartigen Algorithmus nicht daraus lernen?

Obwohl dieser Algorithmus bereits sehr gut ist, gibt es im oben genannten Algorithmusprogramm noch Verbesserungsmöglichkeiten.

Das obige ist der detaillierte Inhalt vonSo implementieren Sie eine schnelle Sortierung in PHP. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!