Implémentation et analyse de l'efficacité de quatre algorithmes de tri dans les compétences PHP

Implémentation et analyse de l'efficacité de quatre algorithmes de tri dans les compétences PHP_php

jacklove

Libérer： 2023-04-01 19:50:02

original

1549 Les gens l'ont consulté

Cet article présente principalement la mise en œuvre et l'analyse de l'efficacité des quatre algorithmes de tri de PHP.Il analyse la définition spécifique, l'utilisation et l'analyse de la complexité des algorithmes du tri à bulles PHP, du tri par insertion, du tri par sélection et du tri rapide sur la base d'exemples spécifiques. doit avoir une valeur de référence. Les amis dans le besoin peuvent s'y référer

Cet article décrit la mise en œuvre et l'analyse de l'efficacité de quatre algorithmes de tri en PHP. Partagez-le avec tout le monde pour votre référence, les détails sont les suivants :

Les quatre algorithmes de tri de base de PHP sont : le tri à bulles, le tri par insertion, le tri par sélection et le tri rapide.

Voici le code de l'algorithme que j'ai compilé :

1. Tri des bulles :

Idée : effectuer plusieurs tours de bulles sur le tableau, chacun temps En un tour, les éléments du tableau sont comparés par paires, les positions sont ajustées et le plus grand nombre émerge.

//简单版：
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;
}

Copier après la connexion

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

Copier après la connexion

Afin d'améliorer l'efficacité de l'algorithme de tri à bulles, les principaux domaines à améliorer sont :

(1) Réduisez le nombre de tours de bulles : lorsqu'aucun échange de position ne se produit dans un tour de tri à bulles, cela signifie que le tableau a été trié et que la boucle doit être quittée immédiatement.

(2) Réduire le nombre de comparaisons à chaque tour : ne plus comparer certains des éléments du tableau qui ont été triés.

2. Tri par insertion :

Idée : Supposons que les éléments devant le tableau soient triés, parcourez les éléments à l'arrière du tableau et recherchez dans la file d'attente des éléments triés Trouvez un emplacement approprié et insérez-le.

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

Copier après la connexion

3. Tri des sélections :

Idée : Faites plusieurs sélections et sélectionnez la plus grande à chaque fois. L'élément est placé à la position spécifiée.

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

Copier après la connexion

4. Tri rapide :

Idée : algorithme récursif. Sélectionnez d'abord le premier élément du tableau comme standard, puis placez les nombres inférieurs ou égaux et supérieurs à lui dans deux tableaux respectivement, effectuez le même traitement sur les deux tableaux, et enfin fusionnez les deux tableaux avec les premiers éléments. .

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

Copier après la connexion

La complexité temporelle et la complexité spatiale de chaque algorithme de tri :

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

Remarque : le tri rapide est plus efficace lorsque le tableau est en panne, et le moins efficace lorsque le tableau est ordonné.

PS : Voici un autre outil de démonstration sur le tri recommandé pour votre référence :

Animation en ligne Démonstration d'insertion/ outils de processus d'algorithme de sélection/bulle/fusion/Hill/tri rapide :
http://tools.jb51.net/aideddesign/paixu_ys