Implementierung und Effizienzanalyse von vier Sortieralgorithmen in PHP [Bubble Sort, Insertion Sort, Selection Sort und Quick Sort]

Dieser Artikel stellt hauptsächlich die Implementierung und Effizienzanalyse der vier Sortieralgorithmen von PHP vor. Er analysiert die spezifische Definition, Verwendung und Algorithmuskomplexitätsanalyse von PHP-Blasensortierung, Einfügungssortierung, Auswahlsortierung und Schnellsortierung Muss von Referenzwert sein. Freunde in Not können sich darauf beziehen

Dieser Artikel beschreibt die Implementierung und Effizienzanalyse von vier Sortieralgorithmen in PHP. Teilen Sie es als Referenz mit allen. Die Details lauten wie folgt:

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

//改进版：
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;
}

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

(1) Reduzieren Sie die Anzahl der Runden der Blasensortierung: Wenn in einer Runde der Blasensortierung kein Positionsaustausch stattfindet, bedeutet dies, 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: Gehen Sie davon aus, dass die Elemente vor dem Array sortiert sind, durchlaufen Sie die Elemente hinter dem Array und suchen Sie darin Suchen Sie in der sortierten Elementwarteschlange einen geeigneten Ort und fügen Sie ihn ein.

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

3. Auswahlsortierung:

Idee: Treffen Sie mehrere Auswahlen und wählen Sie jedes Mal das größte Element aus. Geben Sie das ein angegebenen Ort.

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

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 quickSort($arr)
{
   $n = count($arr);
   if($n <= 1) { //若数组只有一个元素，直接返回
     return $arr;
   }
   $largeArr = array(); //存放大数
  $smallArr = array(); //存放小数
   $cur = $arr[0];  //分类基数
   for($i=1;$i<$n;$i++) { //遍历数组元素，对每个元素进行归类
     if($arr[$i] > $cur) {
       $largeArr[] = $arr[$i];
     } else {
       $smallArr[] = $arr[$i];
     }
   }
   //分别对大数组和小数组进行相同的处理
   $smallArr = quickSort($smallArr);
   $largeArr = quickSort($largeArr);
   //合并小数组、分类基数和大数组
   return array_merge($smallArr,array($cur),$largeArr);
}

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, und am wenigsten effizient, wenn das Array geordnet ist.

Das obige ist der detaillierte Inhalt vonImplementierung und Effizienzanalyse von vier Sortieralgorithmen in PHP [Bubble Sort, Insertion Sort, Selection Sort und Quick Sort]. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!