Quels sont les algorithmes couramment utilisés en PHP ?

Il existe quatre algorithmes de base liés à PHP, à savoir : le tri à bulles, le tri rapide, le tri par sélection, le tri par insertion

1 : Le tri à bulles méthode

Introduction : (Apprentissage recommandé : Programmation PHP du débutant à compétent)

Le tri à bulles est un algorithme de tri simple. Il parcourt à plusieurs reprises la séquence à trier, en comparant les deux éléments tour à tour et en les échangeant s'ils sont dans le mauvais ordre.

Le travail de visite de la séquence est répété jusqu'à ce qu'il n'y ait plus d'échanges nécessaires, ce qui signifie que la séquence a été triée. Le nom de cet algorithme vient du fait que des éléments de plus en plus petits « flotteront » lentement vers le haut du tableau grâce à l'échange.

Étapes :

① : Comparez les éléments adjacents. Si le premier est plus grand que le second, échangez-les tous les deux

② : Faites de même pour chaque paire d'éléments adjacents, en commençant par la première paire et en terminant par la dernière paire. À ce stade, le dernier élément doit être le plus grand nombre.

③ : Répétez les étapes ci-dessus pour tous les éléments sauf le dernier.

④ : Continuez à répéter les étapes ci-dessus pour de moins en moins d'éléments à chaque fois jusqu'à ce qu'il ne reste plus de paire de chiffres. pour comparer

code spécifique :

$arr=array(1,43,54,62,21,66,32,78,36,76,39);
  function bubbleSort ($arr)
  {
  $len = count($arr);
  //该层循环控制 需要冒泡的轮数
  for ($i=1; $i<$len; $i++) {
  //该层循环用来控制每轮 冒出一个数 需要比较的次数
  for ($k=0; $k<$len-$i; $k++) {
  if($arr[$k] > $arr[$k+1]) {
  $tmp = $arr[$k+1]; // 声明一个临时变量
  $arr[$k+1] = $arr[$k];
  $arr[$k] = $tmp;
  }
  }
  }
  return $arr;
  }

2 : Méthode de tri par sélection

Le tri par sélection est un algorithme de tri simple et intuitif . Son principe de fonctionnement est le suivant : tout d'abord, recherchez le plus petit élément de la séquence non triée, stockez-le à la position de départ de la séquence triée, puis continuez à rechercher le plus petit élément parmi les éléments non triés restants. Placez-le ensuite à la fin de la séquence de tri. Et ainsi de suite jusqu'à ce que tous les éléments soient triés.

Code spécifique :

  //实现思路 双重循环完成，外层控制轮数，当前的最小值。内层 控制的比较次数
  function select_sort($arr) {
  //$i 当前最小值的位置， 需要参与比较的元素
  for($i=0, $len=count($arr); $i<$len-1; $i++) {
 //先假设最小的值的位置
  $p = $i;
  //$j 当前都需要和哪些元素比较，$i 后边的。
  for($j=$i+1; $j<$len; $j++) {
  //$arr[$p] 是 当前已知的最小值
 if($arr[$p] > $arr[$j]) {
 //比较，发现更小的,记录下最小值的位置；并且在下次比较时，应该采用已知的最小值进行比较。
 $p = $j;
 }
 }
 //已经确定了当前的最小值的位置，保存到$p中。
 //如果发现 最小值的位置与当前假设的位置$i不同，则位置互换即可
 if($p != $i) {
 $tmp = $arr[$p];
 $arr[$p] = $arr[$i];
 $arr[$i] = $tmp;
 }
 }
 //返回最终结果
 return $arr;
 }

3 : Tri par insertion

La description de l'algorithme de tri par insertion est un algorithme de tri simple et intuitif. Il fonctionne en construisant une séquence ordonnée pour les données non triées, il analyse d'arrière en avant dans une séquence triée pour trouver la position correspondante et l'insérer.

Dans la mise en œuvre du tri par insertion, le tri sur place est généralement utilisé (c'est-à-dire un tri qui ne nécessite que O(1) d'espace supplémentaire. Par conséquent, pendant le processus de numérisation d'arrière en avant, cela est nécessaire). pour trier à plusieurs reprises les éléments triés. Les éléments finaux sont progressivement déplacés vers l'arrière pour laisser de l'espace aux derniers éléments à insérer.

Étapes :

① En partant du premier élément, qui peut être considéré comme ayant été trié

② Sortir l'élément suivant, après lui a été trié Scannez la séquence d'éléments d'arrière en avant

③ Si l'élément (trié) est plus grand que le nouvel élément, déplacez l'élément à la position suivante

④ Répétez l'étape ③ jusqu'à ce que vous trouver l'élément trié est inférieur ou égal à la position du nouvel élément

⑤ Insérer le nouvel élément dans la position

⑥ Répéter l'étape ②

Code spécifique :

  function insert_sort($arr)
  {
  $len=count($arr);
  for($i=1; $i<$len; $i++) {
 //获得当前需要比较的元素值。
  $tmp = $arr[$i];
  //内层循环控制 比较 并 插入
  for($j=$i-1; $j>=0; $j--) {
  //$arr[$i];//需要插入的元素; $arr[$j];//需要比较的元素 
    if($tmp < $arr[$j]) {
 //发现插入的元素要小，交换位置
 //将后边的元素与前面的元素互换
     $arr[$j+1] = $arr[$j];
 //将前面的数设置为 当前需要交换的数
     $arr[$j] = $tmp;
     } else {
 //如果碰到不需要移动的元素
 //由于是已经排序好是数组，则前面的就不需要再次比较了。
     break;
     }
 }
 }
 //将这个元素 插入到已经排序好的序列内。
 //返回
 return $arr;
 }

4 : Tri rapide

Introduction :

Le tri rapide est une méthode développée par Algorithme de tri de Tony Hall. En moyenne, le tri de n éléments nécessite des comparaisons O(n log n).

Dans le pire des cas, des comparaisons O(n2) sont nécessaires, mais cette situation est rare. En fait, le tri rapide est souvent beaucoup plus rapide que les autres algorithmes O(n log n) car sa boucle interne peut être implémentée efficacement sur la plupart des architectures et pour la plupart des données du monde réel. Il est possible de déterminer des choix de conception qui réduisent quadratiquement le temps requis. .

Étapes :

① Choisissez un élément de la séquence, appelé « ligne de base »

② Répétez la séquence de tri, tous les éléments sont meilleurs que la valeur de base Les petits sont placés devant la base, et tous les éléments plus grands que la base sont placés derrière la base (le même nombre peut aller de chaque côté). Une fois cette partition terminée, la base se trouve au milieu de la séquence. C'est ce qu'on appelle une opération de partition

③ Trier récursivement le sous-tableau d'éléments plus petits que la valeur de base et le sous-tableau d'éléments plus grands que la valeur de base

Code spécifique :

  function quick_sort($arr)
  {
  //判断参数是否是一个数组
  if(!is_array($arr)) return false;
  //递归出口:数组长度为1，直接返回数组
  $length = count($arr);
  if($length<=1) return $arr;
  //数组元素有多个,则定义两个空数组
  $left = $right = array();
 //使用for循环进行遍历，把第一个元素当做比较的对象
 for($i=1; $i<$length; $i++)
 {
 //判断当前元素的大小
 if($arr[$i]<$arr[0]){
 $left[]=$arr[$i];
 }else{
 $right[]=$arr[$i];
 }
 }
 //递归调用
 $left=quick_sort($left);
 $right=quick_sort($right);
 //将所有的结果合并
 return array_merge($left,array($arr[0]),$right);
 }

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!