Résumé de la mise en œuvre de l'algorithme de tri PHP

Cette fois, je vais vous apporter un résumé de la mise en œuvre de l'algorithme de tri PHP. Quelles sont les précautions pour la mise en œuvre de l'algorithme de tri PHP. Ce qui suit est un cas pratique, jetons un coup d'œil. .

Les exemples de cet article décrivent l'implémentation 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 : tri à bulles, tri par insertion, tri par sélection et 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;
}

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

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

(1) Réduire le nombre de tours de bulles : lorsqu'un tour de tri à bulles Lorsqu'aucun échange de position ne se produit, 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 é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 derrière le tableau , et recherchez la position appropriée dans la file d'attente des éléments triés et insérez-la dedans.

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. Tri des sélections :

Idée : Faites plusieurs sélections, et sélectionnez à chaque fois l'élément le plus grand et placez-le dans 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;
}

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

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

排序算法	最好时间分析	最差时间分析	平均时间复杂度	稳定度	空间复杂度
冒泡排序	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)

Remarque : le tri rapide est plus efficace lorsque le tableau est en panne. , l'efficacité est la pire lorsque le tableau est trié.

Je pense que vous maîtrisez la méthode après avoir lu le cas dans cet article. Pour des informations plus intéressantes, veuillez prêter attention aux autres articles connexes sur le site Web chinois de php !

Lecture recommandée :

Résumé de la façon dont PHP obtient les extensions de fichiers

PHP utilise Curl pour simuler la connexion et capturer des données Détaillé explication des étapes

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!