Prinzip und Zusammenfassung des PHP-Sortieralgorithmus

Blasensortierungsprinzip

Prinzipbeschreibung:

Vergleichen Sie zwei benachbarte Elemente gleichzeitig, das größere Element wird nach hinten und das kleinere Element nach vorne verschoben ( Standort tauschen). bis das größte Element gefunden ist. Genau wie Blasen sinken große nach unten und kleine steigen nach oben.

Prozess:

Es gibt ein ungeordnetes Array $arr = [8, 9, 3, 6, 1, 4]

第一次外循环 ：找出最大值 9，要俩俩相比，比 5 次。
8 9 3 6 1 4 第一次， 8 跟 9 比，9 大，所以没有交换位置。
8 3 9 6 1 4 第二次， 9 跟 3 比， 9 大，交换位置。
8 3 6 9 1 4 第三次， 9 跟 6 比， 9 大，交换位置。
8 3 6 1 9 4 第四次， 9 跟 1 比， 9 大，交换位置。
8 3 6 1 4 9 第五次， 9 跟 4 比， 9 大，交换位置。
第二次外循环：找出第二大值 8，要俩俩相比，比 4 次。因为上一步已经找到最大值了。
3 8 6 1 4 9 第一次，8 跟 3 比，8 大， 交换位置。
3 6 8 1 4 9 第二次，8 跟 6 比，8 大， 交换位置。
3 6 1 8 4 9 第三次，8 跟 1 比，8 大， 交换位置。
3 6 1 4 8 9 第四次，8 跟 4 比，8 大， 交换位置。
第三次外循环：找出第三大的值 6，要俩俩相比，比三次。
3 6 1 4 8 9 第一次，3 跟 6 比，6 大，位置没有变化。
3 1 6 4 8 9 第二次，6 跟 1 比，6 大，交换位置。
3 1 4 6 8 9 第三次，6 跟 4 比，6 大，交换位置。
第四次外循环：找出第四大的值 4，要俩俩相比，比 2 次。
1 3 4 6 8 9 第一次， 3 跟 1 比， 3 大，交换位置。
1 3 4 6 8 9 第二次， 3 跟 4 比， 4 大，位置不变。
第五次外循环：找出第五大的值 3， 比一次就够了。
1 3 4 6 8 9 比一次。1 跟 3 比，3 大，位置没有变化。

Zusammenfassung:

1. Die äußere Schleife erfordert die Anzahl der Elemente – 1 Mal. Verantwortlich für die Ermittlung des Maximalwerts.

2. Die innere Schlaufe nimmt Schicht für Schicht einmal ab. Verantwortlich für den Vergleich der beiden und den Austausch der Elementpositionen.

Code:

<?php
        function bubbleSort($arr) 
        {
            $len = count($arr);//获取元素个数
            for ($i = 0; $i < $len - 1; $i ++) {//找出最大值
                $flag = 0;//做一个标记
                for($j = 0; $j < $len - 1 - $i; $j++) {//俩俩相比较，交换位置
                    if ($arr[$j] > $arr[$j + 1]) {
                        //$temp = $arr[$j];//存当前元素
                        //$arr[$j] = $arr[$j + 1];//把当前元素的值换成下一个元素的值
                        //$arr[$j + 1] = $temp;//把下一个元素的值换成上一个元素的值。
                        list($arr[$j], $arr[$j + 1]) = [$arr[$j + 1], $arr[$j]];//来自lovecn的评论，有时候思维有些固化。
                        $flag = 1;//交换位置就记录。
                    }
                }
                if ($flag == 0) {//没有发生交换位置，说明排序已经完成。可以推出循环。
                    break;
                }
            }
            return $arr;
        }

Schnellsortierprinzip (rekursiv)

Prinzipbeschreibung:

Aus Array Nehmen Sie den ersten Wert als Referenzobjekt, platzieren Sie den Wert, der kleiner als dieser Wert ist, links und den Wert, der größer als dieser Wert ist, rechts, sodass zwei neue Arrays vorhanden sind. Verarbeiten Sie die beiden Arrays rekursiv und dann die Referenz Objekt links, Zusammenführen rechts. Hinweis: Wenn eine Rekursion vorliegt, müssen Sie den rekursiven Ausgang finden, andernfalls wird die Rekursion fortgesetzt.

Prozess:

Es ist zu schwierig, den Prozess in Worten zu beschreiben, deshalb habe ich im Internet ein Bild gefunden, der Prozess ist sehr klar.

Code:

    <?php
        function quickSort($arr)
        {
            $len = count($arr);
            //递归出口
            if($len <= 1) {
                return $arr;
            }
            $markValue = $arr[0];//参照物。
            $left = $right = [];//定义左边和右边。
            for($i = 1; $i < $len; $i++) {//从1开始循环，因为第一个元素当作参照物。
                if($arr[$i] > $markValue) {//大于参照物的放在右边。
                    $right[] = $arr[$i];
                } else {//小于和等于参照物的元素都放进左边，这样会避免如果数组有重复元素时，会漏掉元素。
                    $left[] = $arr[$i];
                }
            }
            return array_merge(quickSort($left), [$markValue], quickSort($right));
        }

Einfügesortierung

Prinzipbeschreibung:

Zu sortieren Das Array wird in zwei Teile geteilt, das erste Element des Arrays wird in die geordnete Menge eingefügt und die übrigen Elemente werden in die ungeordnete Menge eingefügt. Vergleichen Sie die zu sortierende Zahl von hinten nach vorne mit den zuvor sortierten Daten, bis Sie eine Zahl finden, die kleiner oder gleich dieser Zahl ist, und fügen Sie sie an der entsprechenden Position ein.

Meine Speichermethode:

Angenommen, es gibt zwei Felder. Das erste Feld ist transparent und leer und dient zur Aufnahme von Sequenzelementen. Das zweite Feld ist undurchsichtig und enthält ungeordnete Elemente . (Eigentlich kannst du so tun, als wärst du alles, was dir gefällt und was dir leicht zu merken ist, ist am besten.)

1. Schritt eins: Nehmen Sie ein Element aus der undurchsichtigen Box und werfen Sie es direkt in die transparente Box
2. Schritt zwei: Nehmen Sie ein weiteres Element aus der undurchsichtigen Box und legen Sie es davor Vergleichen Sie die transparente Box. Wenn es groß ist, legen Sie es nach hinten; wenn es klein ist, legen Sie es nach vorne.
3. Wiederholen Sie den zweiten Schritt, aber die Anzahl der Vergleiche, die wir durchführen müssen, erhöht sich jedes Mal, da sich mehr Elemente in der transparenten Box befinden, bis wir die richtige Position gefunden haben.

Prozess:

<?php
    function insertSort($arr)
    {
        $len = count($arr);
        if ($len <= 1) {//一个元素或者没有元素，排序无意义。
            return $arr;
        }
        for($i = 0; $i < $len - 1; $i++) {
            for($j = $i + 1; $j > 0; $j--){//每次比较次数增加。因为有序集合元素在增加。
                if ($arr[$j] < $arr[$j - 1]) {
                    list($arr[$j], $arr[$j - 1]) = [$arr[$j - 1], $arr[$j]];//交换位置。
                }
            }
        }
        return $arr;
    }

Auswahlsortierung

Prinzipbeschreibung:

Einmal um a time Entfernt das minimale oder maximale Element aus dem Array und platziert es an der angegebenen Position.

Schritt eins: Geben Sie dem ersten Element einen Heiligen Feuerbefehl und vergleichen Sie ihn mit jedem nachfolgenden Element (ich nehme das kleinste Element). Wenn Sie auf ein Element stoßen, das kleiner ist als es, geben Sie ihm die Marke „Heiliges Feuer“ und geben Sie die Marke „Heiliges Feuer“ dem kleinsten Element.

Schritt 2: Tauschen Sie die Positionen, übergeben Sie den Heiligen Feuerbefehl an den zweiten Bruder, Element, und wiederholen Sie den ersten Schritt.

Prozess:

<?php
    function selectSort($arr)
    {
        $len = count($arr);
        if ($len <= 1) {//一个元素或者没有元素，排序没有意义。
            return $arr;
        }
        for($i = 0; $i < $len - 1; $i++) {
            $p = $i;//给第一个元素圣火令。
            for($j =  $i + 1; $j < $len; $j++) {
                if ($arr[$j] < $arr[$p]) {//有圣火令的元素和后面的元素比较，把圣火令交给较小的元素。
                    $p = $j;
                }
            }
            list($arr[$p], $arr[$i]) = [$arr[$i], $arr[p]];
        }
        return $arr;
    }

Das obige ist der detaillierte Inhalt vonPrinzip und Zusammenfassung des PHP-Sortieralgorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!