Sechs häufig verwendete Sortieralgorithmen in PHP-PHP-Tutorial-php.cn

Sechs häufig verwendete Sortieralgorithmen in PHP

巴扎黑

Freigeben： 2016-11-21 10:29:40

Original

1032 Leute haben es durchsucht

1. Einfügungssortierung
Verwenden Sie einfache Wörter, um beispielsweise $arr = array(4,2,4,6,3,6,1,7,9) zu beschreiben Nacheinander:
Vergleichen Sie also zuerst das zweite Element des Arrays mit dem ersten Element. Wenn das erste Element größer als das zweite Element ist, tauschen Sie dann die Positionen der beiden. , vergleichen Sie es mit dem zweiten bzw. ersten Element. Wenn das dritte Element kleiner ist, tauschen Sie sie aus. 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). Der PHP-Implementierungscode lautet wie folgt:

<?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; 
         }
?>

Nach dem Login kopieren

2. Auswahlsortierung

Wenn die Auswahlsortierung in der Sprache beschrieben wird, es kann so sein, wie zum Beispiel: $arr = array(4,3,5,2,1);
Vergleichen Sie zuerst die erste und alle folgenden Zahlen, finden Sie die kleinste Zahl und tauschen Sie sie dann mit der ersten aus Array (Wenn natürlich die erste die kleinste ist, muss sie nicht ausgetauscht werden) und dann eine Schleife, das heißt: Vergleichen Sie die zweite mit der folgenden, finden Sie die kleinste Zahl und tauschen Sie sie dann aus es mit der zweiten Zahl usw. Das heißt, es wird jedes Mal der kleinste verbleibende Wert gefunden. 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 ist ebenfalls O(n^2);

php-Implementierungscode ist wie folgt:

<?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; 
         }
?>

Nach dem Login kopieren

3 Blasensortierung ist eigentlich die Summe der Auswahl Es gibt keinen signifikanten Unterschied im Ranking. 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:

4. Schnelle Sortierung

<?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; 
         }
?>

Nach dem Login kopieren

Schnelle Sortierung, um es in der Sprache zu beschreiben, wählt einen Wert $a aus dem Array aus und vergleicht ihn dann mit Die restlichen Elemente werden im Array rechts platziert, andernfalls wird es im Array links platziert. 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:

5. Zusammenführungssortierung

<?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; 
         }
?>

Nach dem Login kopieren

Tatsächlich ist die Zusammenführungssortierung eine Idee des Teilens und Zusammenführens. 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.

6. Heap-Sortierung

<?php
function gbSort($arr){
       if(count($arr)<=1){return $arr;}
       $min = floor(count($arr)/2);//取中间数字进行拆分
       $left = array_slice($arr,0,$min);
       $right = array_slice($arr,$min);
       $left = gbSort($left);  //递归
       $right = gbSort($right);
       return get_merge($left,$right);//调用排序合并函数进行合并
}
function get_merge($left,$right){
        while(count($left) && count($right)){
               $m[] = $left[0]>$right[0] ? array_shift($right) : array_shift($left);
               //进行比较，小的移除，并且放入到数组$m中。
        }
        return arr_merge($m,$left,$right);//进行合并（由于不知道left right 哪个会为空，所以进行统一合并）
}
?>

Nach dem Login kopieren

Fortsetzung folgt