Principe et résumé de l'algorithme de tri PHP

Principe du tri des bulles

Description du principe :

Comparez deux éléments adjacents à la fois, le plus grand élément est reculé et le plus petit élément est avancé ( échanger l'emplacement). jusqu'à ce que le plus grand élément soit trouvé. Tout comme les bulles, les grosses descendent vers le bas et les petites montent vers le haut.

Processus :

Il existe un tableau non ordonné $arr = [8, 9, 3, 6, 1, 4]

第一次外循环 ：找出最大值 9，要俩俩相比，比 5 次。
8 9 3 6 1 4 第一次， 8 跟 9 比，9 大，所以没有交换位置。
8 3 9 6 1 4 第二次， 9 跟 3 比， 9 大，交换位置。
8 3 6 9 1 4 第三次， 9 跟 6 比， 9 大，交换位置。
8 3 6 1 9 4 第四次， 9 跟 1 比， 9 大，交换位置。
8 3 6 1 4 9 第五次， 9 跟 4 比， 9 大，交换位置。
第二次外循环：找出第二大值 8，要俩俩相比，比 4 次。因为上一步已经找到最大值了。
3 8 6 1 4 9 第一次，8 跟 3 比，8 大， 交换位置。
3 6 8 1 4 9 第二次，8 跟 6 比，8 大， 交换位置。
3 6 1 8 4 9 第三次，8 跟 1 比，8 大， 交换位置。
3 6 1 4 8 9 第四次，8 跟 4 比，8 大， 交换位置。
第三次外循环：找出第三大的值 6，要俩俩相比，比三次。
3 6 1 4 8 9 第一次，3 跟 6 比，6 大，位置没有变化。
3 1 6 4 8 9 第二次，6 跟 1 比，6 大，交换位置。
3 1 4 6 8 9 第三次，6 跟 4 比，6 大，交换位置。
第四次外循环：找出第四大的值 4，要俩俩相比，比 2 次。
1 3 4 6 8 9 第一次， 3 跟 1 比， 3 大，交换位置。
1 3 4 6 8 9 第二次， 3 跟 4 比， 4 大，位置不变。
第五次外循环：找出第五大的值 3， 比一次就够了。
1 3 4 6 8 9 比一次。1 跟 3 比，3 大，位置没有变化。

Résumé :

1. La boucle externe nécessite le nombre d'éléments - 1 fois. Responsable de trouver la valeur maximale.

2. La boucle intérieure diminue une fois couche par couche. Responsable de la comparaison des deux et de l’échange des positions des éléments.

Code :

<?php
        function bubbleSort($arr) 
        {
            $len = count($arr);//获取元素个数
            for ($i = 0; $i < $len - 1; $i ++) {//找出最大值
                $flag = 0;//做一个标记
                for($j = 0; $j < $len - 1 - $i; $j++) {//俩俩相比较，交换位置
                    if ($arr[$j] > $arr[$j + 1]) {
                        //$temp = $arr[$j];//存当前元素
                        //$arr[$j] = $arr[$j + 1];//把当前元素的值换成下一个元素的值
                        //$arr[$j + 1] = $temp;//把下一个元素的值换成上一个元素的值。
                        list($arr[$j], $arr[$j + 1]) = [$arr[$j + 1], $arr[$j]];//来自lovecn的评论，有时候思维有些固化。
                        $flag = 1;//交换位置就记录。
                    }
                }
                if ($flag == 0) {//没有发生交换位置，说明排序已经完成。可以推出循环。
                    break;
                }
            }
            return $arr;
        }

Principe de tri rapide (récursif)

Description du principe :

À partir d'un tableau Prenez la première valeur comme objet de référence, mettez la valeur inférieure à cette valeur à gauche et placez la valeur supérieure à cette valeur à droite, il y aura donc deux nouveaux tableaux, traitez récursivement les deux tableaux, puis la référence objet à gauche, Fusionner à droite. Remarque : S'il y a récursion, vous devez trouver la sortie récursive, sinon la récursion continuera.

Processus :

C'est trop difficile de décrire le processus avec des mots, alors j'ai trouvé une image sur Internet, le processus est très clair.

Code :

    <?php
        function quickSort($arr)
        {
            $len = count($arr);
            //递归出口
            if($len <= 1) {
                return $arr;
            }
            $markValue = $arr[0];//参照物。
            $left = $right = [];//定义左边和右边。
            for($i = 1; $i < $len; $i++) {//从1开始循环，因为第一个元素当作参照物。
                if($arr[$i] > $markValue) {//大于参照物的放在右边。
                    $right[] = $arr[$i];
                } else {//小于和等于参照物的元素都放进左边，这样会避免如果数组有重复元素时，会漏掉元素。
                    $left[] = $arr[$i];
                }
            }
            return array_merge(quickSort($left), [$markValue], quickSort($right));
        }

Tri par insertion

Description du principe :

À trier Le tableau est divisé en deux parties, le premier élément du tableau est placé dans l’ensemble ordonné et les éléments restants sont placés dans l’ensemble non ordonné. Comparez le nombre à trier avec les données précédemment triées d'arrière en avant jusqu'à ce que vous trouviez un nombre qui lui est inférieur ou égal, et insérez-le dans la position correspondante.

Ma méthode de mémoire :

Supposons qu'il y ait deux boîtes. La première boîte est transparente et vide, et est utilisée pour contenir des éléments de séquence. La deuxième boîte est opaque et pleine, contenant des éléments non ordonnés. . (En fait, vous pouvez prétendre être n'importe quoi, ce que vous voulez et c'est facile à retenir, c'est le mieux).

1. Première étape : Récupérez un élément de la boîte opaque et jetez-le directement dans la boîte transparente
2. Deuxième étape : Sortez un autre élément de la boîte opaque et placez-le devant la boîte transparente, faites une comparaison. S'il est grand, mettez-le à l'arrière ; s'il est petit, mettez-le devant.
3. Répétez la deuxième étape, mais le nombre de comparaisons que nous devons faire à chaque fois augmente car il y a plus d'éléments dans la boîte transparente jusqu'à ce que nous trouvions la bonne position.

Processus :

<?php
    function insertSort($arr)
    {
        $len = count($arr);
        if ($len <= 1) {//一个元素或者没有元素，排序无意义。
            return $arr;
        }
        for($i = 0; $i < $len - 1; $i++) {
            for($j = $i + 1; $j > 0; $j--){//每次比较次数增加。因为有序集合元素在增加。
                if ($arr[$j] < $arr[$j - 1]) {
                    list($arr[$j], $arr[$j - 1]) = [$arr[$j - 1], $arr[$j]];//交换位置。
                }
            }
        }
        return $arr;
    }

Tri par sélection

Description du principe :

Une fois à a time Supprimez l'élément minimum ou l'élément maximum du tableau et placez-le à la position spécifiée.

Première étape : donnez au premier élément un Ordre du Feu Sacré et comparez-le avec chaque élément suivant (je prends le plus petit élément). Si vous rencontrez un élément plus petit que lui, donnez-lui le jeton du Feu sacré jusqu'à ce que vous sachiez comment donner le jeton du Feu sacré au plus petit élément.

Étape 2 : Échangez vos positions, remettez l'Ordre du Feu sacré au deuxième frère, Élément, et répétez la première étape.

Processus :

<?php
    function selectSort($arr)
    {
        $len = count($arr);
        if ($len <= 1) {//一个元素或者没有元素，排序没有意义。
            return $arr;
        }
        for($i = 0; $i < $len - 1; $i++) {
            $p = $i;//给第一个元素圣火令。
            for($j =  $i + 1; $j < $len; $j++) {
                if ($arr[$j] < $arr[$p]) {//有圣火令的元素和后面的元素比较，把圣火令交给较小的元素。
                    $p = $j;
                }
            }
            list($arr[$p], $arr[$i]) = [$arr[$i], $arr[p]];
        }
        return $arr;
    }

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!