[Interview PHP] Explication de deux algorithmes de tri simples qui doivent être demandés lors de l'entretien : le tri à bulles et le tri rapide

De manière générale, face à des entretiens, nous n'avons aucun problème à répondre aux questions de l'entretien. Pour les développeurs PHP, en plus d’être familiers avec les projets qu’ils réalisent, ils doivent également comprendre les algorithmes de base. Partageons les algorithmes qui sont souvent demandés dans les entretiens PHP : le tri à bulles et le tri rapide.

Tri des bulles  : Tri par comparaison un à un

Idée de base :

Visitez à plusieurs reprises la colonne d'éléments pour être trié, comparez tour à tour deux éléments adjacents et échangez-les si leur ordre (par exemple du grand au petit) est erroné. Le travail des éléments en visite est répété jusqu'à ce qu'aucun élément adjacent ne doive être échangé, ce qui signifie que les éléments ont été triés.

Illustration :

1. en comparant respectivement à partir du deuxième élément. Si l'élément précédent est plus grand que l'élément suivant, échangez les deux éléments pour obtenir la valeur la plus grande. Continuez la comparaison vers l'arrière jusqu'à la fin de l'élément du tableau pour obtenir un bouillonnement (bulle une fois, la valeur maximale. du tableau "restant" actuel est obtenu et placé à la "fin" du tableau)

2. A partir de la deuxième fois, la comparaison commence toujours à partir du premier élément, mais seul le tableau est comparé. La longueur doit être de -1 position, et le nombre de comparaisons à chaque fois est de -1

3. Répétez la comparaison jusqu'à ce qu'il n'y ait finalement plus de chiffres à comparer

Code :

$arr = array(3,2,6,0,1,4,7);
        //因为排序需要每次将一个元素与数组的其他元素进行比较，所以需要两层循环来控制
        //外层循环控制冒泡次数
        //内存循环比较每次的大小，得到每次的最大值（泡）
 
        for($i = 0,$length = count($arr);$i < $length;$i++){
        
                 //内存循环
                 for($j = 0;$j < ($length - $i - 1);$j++){
                         //拿着j变量所对应的数组元素，与后面的元素进行比较
                         if($arr[$j] > $arr[$j + 1]){
                                  //交换位置
                                  $temp              = $arr[$j];
                                  $arr[$j]           = $arr[$j+1];
                                  $arr[$j+1]         = $temp;
                         }
                 }
        }

Résumé :

La meilleure complexité temporelle du tri à bulles est O(n). Bien que ce ne soit pas l'algorithme optimal, c'est quelque chose que nous rencontrons souvent et que nous demanderons également lors des entretiens. il faut donc comprendre les principes de base, les comprendre, et être capable de les écrire

Tri rapide : Échanger l'espace contre le temps

Idée de base :

Divisez les données à trier en deux parties indépendantes grâce à un tri en un seul passage. Toutes les données d'une partie sont plus petites que toutes les données de l'autre partie, puis utilisez cette méthode pour trier les deux parties. de données. Le tri rapide est effectué séparément et l'ensemble du processus de tri peut être effectué de manière récursive, de sorte que l'ensemble des données devienne une séquence ordonnée.

Illustration :

Trouver n'importe quel élément du tableau actuel En standard, créez deux tableaux vides et parcourez l'ensemble du tableau. .élément, l'élément parcouru est plus petit que l'élément actuel, puis placez-le dans le tableau de gauche ; s'il est plus grand, placez-le dans un autre tableau

Idée récursive

1. point : Si deux Si les éléments d'un tableau sont supérieurs à 1, ils doivent être décomposés

2. Sortie récursive : lorsque l'élément du tableau devient 1

Code :

//待排序数组
        $arr = array(5,3,8,2,6,4,7);
        //函数实现快速排序
        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);
        }

Résumé :

Le tri rapide est la méthode de tri la plus rapide parmi les méthodes de tri générales. Il est basé sur la récursivité et utilise l'espace pour le temps. Lors des entretiens généraux, il vous sera demandé de connaître les principes de base.

[Tutoriels associés : Tutoriel vidéo PHP]

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!