Zusammenfassung der Implementierung des PHP-Sortieralgorithmus

Dieses Mal werde ich Ihnen eine Zusammenfassung der Implementierung des PHP-Sortieralgorithmus geben. Was sind die Vorsichtsmaßnahmen für die Implementierung des PHP-Sortieralgorithmus? .

Die Beispiele in diesem Artikel beschreiben die Implementierung und Effizienzanalyse von vier Sortieralgorithmen in PHP. Teilen Sie es als Referenz mit allen:

Die vier grundlegenden Sortieralgorithmen von PHP sind: Blasensortierung, Einfügungssortierung, Auswahlsortierung und Schnellsortierung .

Das Folgende ist der Algorithmuscode, den ich kompiliert habe:

1. Blasensortierung:

Idee: Führen Sie jeweils mehrere Blasenrunden auf dem Array durch Zeit In einer Runde werden die Elemente im Array paarweise verglichen, die Positionen angepasst und die größte Zahl entsteht.

//简单版：
function bubbleSort($arr)
{
   $n = count($arr);
   for($i=1;$i<$n;$i++) { //冒泡的轮数(最多$n-1轮)
     for($j=0;$j<$n-1;$j++) { //每一轮冒泡(两两比较，大者后移)
       if($arr[$j] > $arr[$j+1]) { //前者大于后者，交换位置
          $tmp = $arr[$j];
          $arr[$j] = $arr[$j+1];
          $arr[$j+1] = $tmp;
       }
     }
   }
   return $arr;
}

rrree

Um die Effizienz des Blasensortierungsalgorithmus zu verbessern, sind die Hauptbereiche, die verbessert werden müssen:

(1) Reduzieren Sie die Anzahl der Blasenrunden: wenn in a kein Positionsaustausch stattfindet Die Runde der Blasensortierung zeigt an, dass das Array sortiert wurde und die Schleife sofort verlassen werden sollte.

(2) Reduzieren Sie die Anzahl der Vergleiche in jeder Runde: Vergleichen Sie einige Elemente im Array, die sortiert wurden, nicht mehr.

2. Einfügungssortierung:

Idee: Angenommen, die Elemente vor dem Array sind sortiert, die Elemente hinter dem Array durchlaufen , und Suchen Sie die entsprechende Position in der Warteschlange für sortierte Elemente und fügen Sie sie dort ein.

//改进版：
function bubbleSort($arr)
{
   $n = count($arr);
   for($i=1;$i<$n;$i++) { //冒泡的轮数(最多$n-1轮)
     $flag = 0;  //是否发生位置交换的标志
     for($j=0;$j<$n-$i;$j++) { //每一轮冒泡(两两比较，大者后移)
       if($arr[$j] > $arr[$j+1]) { //前者大于后者，交换位置
          $tmp = $arr[$j];
          $arr[$j] = $arr[$j+1];
          $arr[$j+1] = $tmp;
          $flag = 1;
       }
     }
     if($flag == 0) {  //没有发生位置交换，排序已完成
       break;
     }
   }
   return $arr;
}

3. Auswahlsortierung:

Idee: Treffen Sie mehrere Auswahlen und wählen Sie jedes Mal das größte Element aus und platzieren Sie es an der angegebenen Position.

function insertSort($arr)
{
   $n = count($arr);
   for($i=1;$i<$n;$i++) { //从第二个元素开始插入
     for($j=$i-1;$j>=0;$j--) { //与前面的数比较，找到插入的位置
       if($arr[$j] > $arr[$j+1]) { //比前面的数小，交换位置
          $tmp = $arr[$j];
          $arr[$j] = $arr[$j+1];
          $arr[$j+1] = $tmp;
       } else { //大于或等于前面的数，表示已找到插入的位置
          break;
       }
     }
   }
   return $arr;
}

4. Schnelle Sortierung:

Idee: Rekursiver Algorithmus. Wählen Sie zuerst das erste Element des Arrays als Standard aus, geben Sie dann die Zahlen kleiner oder gleich und größer als dieses in zwei Arrays ein, führen Sie die gleiche Verarbeitung für die beiden Arrays durch und führen Sie schließlich die beiden Arrays mit den ersten Elementen zusammen .

function selectSort($arr)
{
   $n = count($arr);
   for($i=$n-1;$i>0;$i--) { //选择排序的轮数($n-1轮)
     $pos = $i; //假设最大元素的位置
     for($j=0;$j<$i;$j++) { //每一轮：从未选择过的元素中选择最大的数
       if($arr[$j] > $arr[$pos]) { //所在位置元素比目前最大元素大，标志其位置
          $pos = $j;
       }
     }
     if($pos != $i) { //将最大元素放入指定的位置
       $tmp = $arr[$pos];
       $arr[$pos] = $arr[$i];
       $arr[$i] = $tmp;
     }
   }
   return $arr;
}

Die zeitliche und räumliche Komplexität jedes Sortieralgorithmus:

排序算法	最好时间分析	最差时间分析	平均时间复杂度	稳定度	空间复杂度
冒泡排序	O(n)	O(n2)	O(n2)	稳定	O(1)
插入排序	O(n)	O(n2)	O(n2)	稳定	O(1)
选择排序	O(n2)	O(n2)	O(n2)	稳定	O(1)
快速排序	O(nlog2n)	O(n2)	O(nlog2n)	不稳定	O(log2n)~O(n)

Hinweis: Die schnelle Sortierung ist am effizientesten, wenn das Array nicht in der richtigen Reihenfolge ist Die Effizienz ist am schlechtesten, wenn das Array sortiert ist.

Ich glaube, dass Sie die Methode beherrschen, nachdem Sie den Fall in diesem Artikel gelesen haben. Weitere spannende Informationen finden Sie in anderen verwandten Artikeln auf der chinesischen PHP-Website!

Empfohlene Lektüre:

Zusammenfassung, wie PHP Dateierweiterungen erhält

PHP verwendet Curl, um Anmeldungen zu simulieren und detaillierte Daten zu erfassen Erklärung der Schritte

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