PHP implementiert 6 Sortieralgorithmen

1. Einfügungssortierung

Beschreiben Sie es einfach mit Worten: $arr = array(4,2,4,6,3,6,1,7,9); So führen Sie eine sequentielle Sortierung durch:
Vergleichen Sie dann zuerst das zweite Element des Arrays mit dem ersten Element. Wenn das erste Element größer als das zweite Element ist, vergleichen Sie anschließend die Positionen der beiden des Arrays mit dem ersten Element werden jeweils mit dem zweiten und ersten Element verglichen. Wenn das dritte Element kleiner ist, werden sie vertauscht. Und so weiter. Dies ist eine Einfügungssortierung und ihre Zeithäufigkeit beträgt: 1 2... (n-1)=(n^2)/2. Dann ist seine Zeitkomplexität O(n^2).

PHP-Implementierungscode ist wie folgt:

PHP-Code

<?php  
        function insertSort($arr){  
              $count = count($arr);  
              if($count<2){  
                  return $arr;   
              }  
              for($i=1;$i<$count;$i++){  
                    $tmp = $arr[$i];  
                     $j=$i-1;  
                     while(j>=0&&$arr[$j]<$arr[$i]){  
                         $arr[$i] = $arr[$j];                        
                         $arr[$j] = $tmp;  
                         $j--;  
                     }  
               }  
               return $arr;   
         }  
?>

Zwei, Auswahlsortierung

Wenn die Auswahlsortierung in der Sprache beschrieben wird, kann sie wie folgt aussehen: $arr = array(4,3,5,2,1)
Vergleichen Sie zuerst die erste eins mit allen folgenden, finde die kleinste Zahl und tausche sie dann mit dem ersten Array aus (wenn das erste das kleinste ist, ist es natürlich nicht nötig, es zu tauschen) und dann eine Schleife, das heißt: vergleiche Die zweite Zahl wird mit der folgenden Zahl vertauscht und es wird ermittelt. Die kleinste Zahl wird dann mit der zweiten Zahl vertauscht usw., was bedeutet, dass jedes Mal der kleinste verbleibende Wert gefunden wird. Es kann erhalten werden: Beim ersten Mal beträgt die Zeitfrequenz n (Vergleichen Sie das erste mit dem folgenden n-1, finden Sie das kleinste und prüfen Sie dann, ob es das erste ist. Wenn nicht, tauschen Sie es aus). die Zukunft, gefolgt von minus eins. Seine zeitliche Komplexität beträgt ebenfalls O(n^2); Blasensortierung

Die Blasensortierung unterscheidet sich eigentlich nicht wesentlich von der Auswahlsortierung. Finden Sie das kleinste und platzieren Sie es ganz links. Lösen Sie die Aufgaben der Reihe nach. Der Unterschied besteht darin, dass die Blasensortierung die Positionen öfter austauscht, während die Auswahlsortierung den Index des kleinsten Elements findet und dann direkt die Positionen mit dem Element ganz links austauscht.
Der PHP-Implementierungscode lautet wie folgt:

PHP-Code

<?php  
        function selectSort($arr){  
  
              $count = count($arr);  
              if($count<2){  
                  return $arr;   
              }  
              for($i=0;$i<$count;$i++){  
                     $min=$i;  
                     for(j=$i+1;$j<$count;$j++){  
                         if($arr[$min]>$arr[$j]){  
                              $min = $j; //找到最小的那个元素的下标  
                         }  
                     }  
                     if($min!=$i){//如果下标不是$i 则互换。  
                            $tmp= $arr[$i];                        
                             $arr[$i] = $arr[$min];  
                             $arr[$min] = $tmp;  
                       }  
               }  
               return $arr;   
         }  
?>

Vier, schnelle Sortierung

Schnelle Sortierung, um es in der Sprache zu beschreiben, Wählen Sie aus dem Array einen Wert $a aus und vergleichen Sie ihn dann mit den anderen Elementen. Wenn er größer als $a ist, fügen Sie ihn in das Array rechts ein und umgekehrt, fügen Sie ihn in das Array links ein. Rufen Sie dann rekursiv links und rechts auf, dh unterteilen Sie links und rechts und führen Sie schließlich die Arrays zusammen.

PHP implementiert die schnelle Sortierung:

PHP-Code

<?php  
        function selectSort($arr){  
  
              $count = count($arr);  
              if($count<2){  
                  return $arr;   
              }  
              for($i=0;$i<$count;$i++){  
                     for(j=$i+1;$j<$count;$j++){  
                         if($arr[$i]>$arr[$j]){  
                              $tmp= $arr[$i];                        
                             $arr[$i] = $arr[$i];  
                             $arr[$i] = $tmp;  
                         }  
                     }  
               }  
               return $arr;   
         }  
?>

5. Zusammenführungssortierung ist tatsächlich eine Idee der Aufteilung und verschmelzen. Es hat etwas mit der Idee der schnellen Sortierung gemeinsam: Ein Stapel links, ein Stapel rechts und dann zusammengeführt. Die Sortierung erfolgt durch Rekursion. Was ist der Unterschied? Der Unterschied zwischen ihnen ist auch ein wesentlicher Unterschied im Denken. Die Aufteilung der Schnellsortierung wählt bestimmte Werte für den Größenvergleich aus und teilt sie so in links und rechts auf. Das heißt, der kleine Stapel wird links und der große Stapel rechts platziert. Dann wird die kleine Linke in left1 und right1 unterteilt. . . . Die Sortierung erfolgt durch eine ähnliche Rekursion. Mit anderen Worten: Wenn Sie es weiter unterteilen, ist left1 am Ende der Rekursion der Mindestwert.

Bei der Zusammenführungssortierung werden die Arrays von links und rechts rekursiv geometrisch in die minimale Granularität von 2 oder 1 unterteilt, dann mit dem Vergleich der Größen begonnen und dann zusammengeführt. Die Vergleichsgröße hier ist: Das linke Element des Sohnes wird mit dem rechten Element des Sohnes verglichen, dann sortiert und mit dem linken oder rechten Element des Vaters zusammengeführt. Bis die letzten beiden Arrays sortiert und zusammengeführt sind: das anfängliche linke und das rechte, kann hier nur ihre jeweilige Reihenfolge nicht bestätigt werden, und die Reihenfolge des gesamten Arrays kann nicht bestätigt werden. Die Zusammenführung muss noch durch den endgültigen Vergleich abgeschlossen werden Links und rechts sortieren im wahrsten Sinne des Wortes.

PHP-Code

<?php  
        function mySort($arr){  
  
              $count = count($arr);  
              if($count<2){  
                  return $arr;   
              }  
              $key = $arr[0];//选择第一个元素作为比较元素，可选其他  
               $left = array();                
               $right = array();  
               for($i=1;$i<$count;$i++){  
                     if($key>=$arr[$i]){  
                         $left[] = $arr[$i];    
                     }else{  
                          $right[] = $arr[$i];  
                      }  
               }  
               $left = mySort($left);  
               $right = mySort($right);  
               $result = array_merge($left,$right);  
               return $result;   
         }  
?>

6. Heap-Sortierung

Fortsetzung folgt