[PHP-Interview] Erläuterung zweier einfacher Sortieralgorithmen, die im Interview gefragt werden müssen: Blasensortierung und Schnellsortierung

Im Allgemeinen haben wir bei Vorstellungsgesprächen kein Problem damit, die Fragen im Vorstellungsgespräch zu beantworten. PHP-Entwickler müssen nicht nur mit den von ihnen durchgeführten Projekten vertraut sein, sondern auch grundlegende Algorithmen verstehen. Lassen Sie uns die Algorithmen vorstellen, die in PHP-Interviews häufig gefragt werden: Blasensortierung und Schnellsortierung.

Blasensortierung : Eins-zu-eins-Vergleichssortierung

Grundidee:

Besuchen Sie die Spalte der Elemente wiederholt sortiert werden, zwei benachbarte Elemente der Reihe nach vergleichen und sie vertauschen, wenn ihre Reihenfolge (z. B. von groß nach klein) falsch ist. Die Arbeit des Besuchs von Elementen wird wiederholt, bis keine benachbarten Elemente mehr ausgetauscht werden müssen, was bedeutet, dass die Elemente sortiert wurden.

Abbildung:

1. Das erste Element des Arrays gedrückt halten, Start Wenn das vorherige Element größer als das spätere Element ist, tauschen Sie die beiden Elemente aus, um den größeren Wert zu erhalten. Setzen Sie den Rückwärtsvergleich bis zum Ende des Array-Elements fort, um eine Blase zu erzielen Der Wert des aktuellen „verbleibenden“ Arrays wird ermittelt und am „Ende“ des Arrays platziert)

2. Ab dem zweiten Mal beginnt der Vergleich immer noch beim ersten Element, es wird jedoch nur das Array verglichen . Die Länge sollte -1 Position betragen und die Anzahl der Vergleiche beträgt jedes Mal -1

3. Wiederholen Sie den Vergleich, bis schließlich keine Zahlen mehr zum Vergleichen vorhanden sind

Code:

$arr = array(3,2,6,0,1,4,7);
        //因为排序需要每次将一个元素与数组的其他元素进行比较，所以需要两层循环来控制
        //外层循环控制冒泡次数
        //内存循环比较每次的大小，得到每次的最大值（泡）
 
        for($i = 0,$length = count($arr);$i < $length;$i++){
        
                 //内存循环
                 for($j = 0;$j < ($length - $i - 1);$j++){
                         //拿着j变量所对应的数组元素，与后面的元素进行比较
                         if($arr[$j] > $arr[$j + 1]){
                                  //交换位置
                                  $temp              = $arr[$j];
                                  $arr[$j]           = $arr[$j+1];
                                  $arr[$j+1]         = $temp;
                         }
                 }
        }

Zusammenfassung:

Die beste Zeitkomplexität der Blasensortierung ist O(n), obwohl es sich nicht um den optimalen Algorithmus handelt, mit dem wir häufig in Berührung kommen und der auch in Interviews gefragt wird. Wir müssen also die Grundprinzipien verstehen, sie verstehen und schreiben können

Schnelle Sortierung: Tauschen Sie Raum gegen Zeit

Grundidee:

Teilen Sie die zu sortierenden Daten durch eine Sortierung in zwei unabhängige Teile auf. Alle Daten in einem Teil sind kleiner als alle Daten im anderen Teil. Verwenden Sie dann diese Methode, um die beiden Teile zu trennen Durch die schnelle Sortierung der Daten kann der gesamte Sortiervorgang rekursiv durchgeführt werden, sodass die gesamten Daten zu einer geordneten Sequenz werden.

Abbildung:

Suchen Sie ein beliebiges Element im aktuellen Array. Erstellen Sie standardmäßig zwei leere Arrays und durchlaufen Sie das gesamte Array . Element, das durchquerte Element ist kleiner als das aktuelle Element. Wenn es größer ist, fügen Sie es in ein anderes Array ein.

Rekursive Idee

1 Punkt: Wenn zwei Elemente eines Arrays größer als 1 sind, müssen sie zerlegt werden

2. Rekursiver Ausgang: wenn das Array-Element 1 wird

Code:

//待排序数组
        $arr = array(5,3,8,2,6,4,7);
        //函数实现快速排序
        function quick_sort($arr){
                 //判断参数是否是一个数组
                 if(!is_array($arr)) return false;
 
                 //递归出口：数组长度为1就直接返回数组
                 $length = count($arr);
                 if($length <= 1) return $arr;

                 //数组元素有多个
                 $left = $right = array();
                 //使用for循环进行遍历，把第一个元素当做比较的对象
                 for($i = 1;$i < $length;$i++){
                         //判断当前元素值的大小
                         if($arr[$i] < $arr[0]){
                                  //当前元素小于标准元素，放到左边数组
                                  $left[] = $arr[$i];
                         }else{
                                  $right[] = $arr[$i];
                         }
                 }
                 //递归调用
                 $left = quick_sort($left);
                 $right = quick_sort($right);
 
                 //将所有的结果合并
                 return array_merge($left,array($arr[0]),$right);
        }

Zusammenfassung:

Schnellsortierung ist die schnellste Sortiermethode unter den allgemeinen Sortiermethoden. Sie basiert auf Rekursion und nutzt Raum für Zeit. In allgemeinen Vorstellungsgesprächen werden Sie gebeten, die Grundprinzipien zu kennen.

[Verwandte Tutorials: PHP-Video-Tutorial]

Das obige ist der detaillierte Inhalt von[PHP-Interview] Erläuterung zweier einfacher Sortieralgorithmen, die im Interview gefragt werden müssen: Blasensortierung und Schnellsortierung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!