Exemple de partage d'algorithmes de tri courants en PHP

• Les algorithmes de tri courants sont : le tri à bulles, le tri rapide, le tri par sélection, le tri par insertion, voici ceux que j'ai préparés pour mon récent entretien Notes d'étude, et je j'espère que cela pourra vous aider.

• Exigence : Trier un tableau avec plusieurs nombres de petit à grand.

Algorithme de tri

【 1]. tri

Analyse d'idées :

Imaginez qu'il y ait N nombre de ballons à hydrogène qui n'ont pas été disposés en séquence dans une grande piscine. Les plus gros sortent en premier, puis les plus petits. monter vers le haut. Autrement dit, deux nombres adjacents sont comparés à chaque fois, le plus petit devant et le plus grand derrière, sinon les positions sont inversées.

Mise en œuvre du code

• (exemple plusieurs méthodes d'écriture, faire attention aux conditions de jugement du corps de la boucle) Il est recommandé de utilisez les premier et deuxième types.

    /**
     * 交换方法
     * @param array $arr 目标数组
     * @param $a 索引a
     * @param $b 索引b
     * @param bool $flag 交换标志
     * @return bool
     */
    function swap(array &$arr,$a,$b,$flag = false){
        // 遍历i后面的元素，只要该元素小于当前元素，就把较小的往前冒泡
        if($arr[$a] > $arr[$b]){            $temp = $arr[$a];            $arr[$a] = $arr[$b];            $arr[$b] = $temp;            $flag = true;
        }        return $flag;
    }    /**
     * 第一种写法
     * @param $arr 所要排序的数组
     * @return mixed 返回的数组
     */
    function bubbleSort($arr) {
        $len = count($arr);        if ($len <= 1) {return $arr;}        //该层循环控制 需要冒泡的轮数
        for ($i = 0; $i < $len-1; $i++) {            //该层循环用来控制每轮 冒出一个数 需要比较的次数
            for ($j = $i + 1; $j < $len; $j++) {                // 或者 $this->swap($arr,$j,$j+1);
                $this->swap($arr,$i,$j);
            }
        }        return $arr;
    }    //第二种写法
    public function BubbleSort2($arr){
        $len = count($arr);        if ($len <= 1) {return $arr;}        for ($i = 0;$i < $len-1;$i++){            //TODO 本趟排序开始前，交换标志应为假
            $flag = false;            for ($j = 0;$j <= $len-2;$j++){                $flag = $this->swap($arr,$j,$j+1,$flag);
            }            if(!$flag) return $arr;
        }        return $arr;
    }    //第三种写法
    function BubbleSort3(array &$arr){
        $len = count($arr);        if ($len <= 1) {return $arr;}        for($i = 0;$i < $len-1;$i++){            //从后往前逐层上浮小的元素 $j >= 0
            for($j = $len - 2;$j >= $i ;$j --){                $this->swap($arr,$j,$j+1);
            }
        }        return $arr;
    }    //第四种写法
    function bubbleSort4($arr)
    {
        $len = count($arr);        if ($len <= 1) {return $arr;}        for($i = 0;$i < $len-1;$i++) {            for($j = 0;$j < $len-$i-1;$j++) {                $this->swap($arr,$j,$j+1);
            }
        }        return $arr;
    }

Résumé :

• Complexité temporelle : O(n^2)

• Supplément : vous pouvez utiliser la fonction intégrée PHP sort() ou rsort().

• La fonction ci-dessus trie le tableau d'index en fonction de la valeur clé, comme unité dans le tableau, attribuez de nouveaux noms de clés, ce qui supprimera les noms de clés d'origine au lieu de simplement les réorganiser. En cas de succès, renvoyez VRAI, sinon renvoyez FAUX

[2]. Sélectionnez le tri

Analyse des idées :

À chaque fois parmi les éléments de données à trié Sélectionnez l'élément le plus petit (ou le plus grand) de la séquence et stockez-le au début de la séquence jusqu'à ce que tous les éléments de données à trier soient disposés

Implémentation du code

    /*
    * @param 选择排序法
    * 每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完
    * */
    function selectSort($arr){
        //双重循环完成，外层控制轮数，内层控制比较次数
        $len = count($arr);        if ($len <= 1) {return $arr;}        for ($i = 0; $i < $len-1; $i++) {            $minIndex = $i;            // 找出i后面最小的元素与当前元素交换
            for ($j = $i + 1; $j < $len; $j++) {                if ($arr[$minIndex] > $arr[$j]){                    $minIndex = $j;
                }
            }            if ($minIndex != $i) {                $temp = $arr[$i];                $arr[$i] = $arr[$minIndex];                $arr[$minIndex] = $temp;
            }
        }        return $arr;
    }

Résumé :

• Complexité temporelle : O(n^2)

• Méthode de tri instable (par exemple, dans la séquence [5, 5, 3], les premiers [5] et [3] sont échangés pour la première fois, provoquant le déplacement des 5 premiers derrière les seconds 5) .

• Dans une sélection, si un élément est plus petit que l'élément courant, et que le petit élément apparaît derrière un élément égal à l'élément courant, alors la stabilité sera détruite après le échange

• Le meilleur des cas est qu'il est déjà en commande et échangé 0 fois ; le pire des cas est échangé n-1 fois et n/2 fois dans l'ordre inverse. Le nombre d'échanges est bien inférieur à celui du tri à bulles. Puisque l'échange nécessite plus de temps CPU que la comparaison, lorsque la valeur n est petite, le tri par sélection est plus rapide que le tri à bulles

【3】. Tri par insertion

Analyse d'idée :

• Insérer un enregistrement à trier au début en fonction de la taille de sa valeur clé à chaque entrez dans la position appropriée dans le fichier trié jusqu'à ce que tous soient insérés. (Obtenant ainsi une nouvelle donnée ordonnée avec le nombre plus un)

• Description :

• ⒈ Dès le premier À partir de l'élément , l'élément peut être considéré comme trié

• ⒉ Sortir l'élément suivant et scanner de l'arrière vers l'avant dans la séquence des éléments triés

• ⒊ 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 3 jusqu'à ce que vous trouviez l'élément trié. inférieur ou égal à la position du nouvel élément

• ⒌ Insérez le nouvel élément dans la position suivante

• ⒍ Répétez les étapes 2 à 5

Implémentation du code

• Deux façons d'écrire sont proposées ici, principalement l'écriture en boucle la méthode est légèrement différente Différent, peut être utilisé pour référence.

    /*
    * 插入排序法
    * 每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。
    * */
    function insertSort($arr){
        $len = count($arr);        if ($len <= 1) {return $arr;}        //先默认$array[0]，已经有序，是有序表
        for($i = 1;$i < $len;$i++){            if ($arr[$i] < $arr[$i-1]){                $insertVal = $arr[$i]; //$insertVal是准备插入的数
                $insertIndex = $i - 1; //有序表中准备比较的数的下标
                while($insertIndex >= 0 && $insertVal < $arr[$insertIndex]){                    $arr[$insertIndex + 1] = $arr[$insertIndex]; //将数组往后挪
                    $insertIndex--; //将下标往前挪，准备与前一个进行比较
                }                if($insertIndex + 1 !== $i){                    $arr[$insertIndex + 1] = $insertVal;
                }
            }
        }        return $arr;
    }    function insertSort2($arr){
        $len = count($arr);        if ($len <= 1) {return $arr;}        //先默认$array[0]，已经有序，是有序表
        for($i = 1;$i < $len;$i++){            if ($arr[$i] < $arr[$i-1]){                $insertVal = $arr[$i]; //$insertVal是准备插入的数
                //$j 有序表中准备比较的数的下标
                //$j-- 将下标往前挪，准备与前一个进行比较
                for ($j = $i-1;$j >= 0 && $insertVal < $arr[$j];$j--){                    $arr[$j+1]= $arr[$j];//将数组往后挪
                }                $arr[$j + 1] = $insertVal;
            }
        }        return $arr;
    }

Résumé :

• Complexité temporelle :

  O(n ^2)

• Complexité spatiale :

  O(1) (utilisé pour enregistrer les données qui doivent être insérées)

• Méthode de tri stable

• l'algorithme convient au tri d'une petite quantité de données

• Si le le coût de l'opération de comparaison est supérieur à celui de l'opération d'échange. La recherche binaire peut être utilisée pour réduire le nombre d'opérations de comparaison. Cet algorithme peut être considéré comme une variante du tri par insertion, appelé tri par recherche binaire.

【IV】.Tri rapide

Analyse des idées :

• Diviser les données à trier en deux parties indépendantes, toutes les données d'une partie sont plus petites que toutes les données de l'autre partie,

• Utilisez ensuite cette méthode pour trier rapidement les deux parties des données respectivement, et l'ensemble du processus de tri. peut être fait de manière récursive, de sorte que les données entières deviennent une séquence ordonnée

代码实现

• 注：网上多数为quick_sort2（）这类的写法，感觉并非原算法的描述，建议可做参考.

• 或许代码quick_sort()有所欠缺，并未发现能有较快的排序效果，尴尬了.

    /**
     * @param $arr 目标数组
     * @param int $l 左起坐标
     * @param $r 右起坐标 初始化传入数组时，$r = count($arr)-1
     * @return mixed
     */
    public  function quick_sort(&$arr, $l=0, $r)
    {
        $length = count($arr);        //先判断是否需要继续进行 递归出口:数组长度为1，直接返回数组
        if(!is_array($arr)||$length <= 1) {return $arr;}        if ($l < $r)
        {            $i = $l;            $j = $r;            $baseVal = $arr[$l];            while ($i < $j)
            {                // 从右向左找第一个小于$baseVal的数
                while($i < $j && $arr[$j] >= $baseVal)                    $j--;                if($i < $j)                    $arr[$i++] = $arr[$j];                // 从左向右找第一个大于等于$baseVal的数
                while($i < $j && $arr[$i] < $baseVal)                    $i++;                if($i < $j)                    $arr[$j--] = $arr[$i];
            }            $arr[$i] = $baseVal;            $this->quick_sort($arr, $l, $i - 1); // 递归调用
            $this->quick_sort($arr, $i + 1, $r);            return $arr;
        }
    }    /*
    * 快速排序法
    * */
    public function quick_sort2($arr) {
        $length = count($arr);        //先判断是否需要继续进行 递归出口:数组长度为1，直接返回数组
        if(!is_array($arr)||$length <= 1) {return $arr;}        //选择第一个元素作为基准
        $baseValue = $arr[0];        //遍历除了标尺外的所有元素，按照大小关系放入两个数组内
        //初始化两个数组
        $leftArr = array();  //小于基准的
        $rightArr = array();  //大于基准的
        //使用for循环进行遍历，把选定的基准当做比较的对象
        for($i = 1; $i<$length; $i++) {            if( $arr[$i] < $baseValue) {                //放入左边数组
                $leftArr[] = $arr[$i];
            } else {                //放入右边数组
                $rightArr[] = $arr[$i];
            }
        }        //再分别对左边和右边的数组进行相同的排序处理方式递归调用这个函数
        $leftArr = $this->quick_sort2($leftArr);        $rightArr = $this->quick_sort2($rightArr);        //合并 左边 标尺 右边， 注意：array($baseValue),关联着重复数据
        return array_merge($leftArr, array($baseValue), $rightArr);
    }

小结：

• 既不浪费空间又可以快一点的排序算法

• 最差时间复杂度O(N^2)，平均时间复杂度为O(NlogN)

• 推荐文章-坐在马桶上看算法：快速排序（注：其中的算法逻辑并非标准逻辑，建议阅读底部的评论，可做参考）

【五】.计数排序

思路分析

• 计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序

• 算法描述：
  

• 找出待排序的数组中最大和最小的元素；

• 统计数组中每个值为i的元素出现的次数，存入数组C的第i项；

• 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；

• 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

代码实现

    /**
     * 计数排序
     * @param $arr
     * @return array
     */
    function countingSort($arr)
    {
        $len = count( $arr );        if( $len <= 1 ) return $arr;        // 找出待排序的数组中最大值和最小值
        $min = min($arr);        $max = max($arr);        // 计算待排序的数组中每个元素的个数
        $countArr = array();        for($i = $min; $i <= $max; $i++)
        {            $countArr[$i] = 0;
        }        foreach($arr as $v)
        {            $countArr[$v] +=  1;
        }        $resArr = array();        foreach ($countArr as $k=>$c) {            for($i = 0; $i < $c; $i++)
            {                $resArr[] = $k;
            }
        }        return $resArr;
    }

小结：

• 计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。
  作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

• 计数排序不是比较排序，排序的速度快于任何比较排序算法

• 最佳情况：T(n) = O(n+k)
  最差情况：T(n) = O(n+k)
  平均情况：T(n) = O(n+k)

• 限制条件很多 注意

【六】.桶排序

思路分析

• 假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排)

• 算法描述
  

• 设置一个定量的数组当作空桶；

• 遍历输入数据，并且把数据一个一个放到对应的桶里去；

• 对每个不是空的桶进行排序；

• 从不是空的桶里把排好序的数据拼接起来。

代码实现

    /**
     * 木桶排序设计
     * @param $arr 目标数组
     * @param int $bucketCount 分配的木桶数目（整数）
     * @return array
     */
    public function bucketSort($arr,$bucketCount = 10)
    {
        $len = count($arr);        $max = max($arr)+1;        if ($len <= 1) {return $arr;}        //填充木桶
        $arrFill = array_fill(0, $bucketCount, []);        //开始标示木桶
        for($i = 0; $i < $len ; $i++)
        {            $key = intval($arr[$i]/($max/$bucketCount));
            array_push($arrFill[$key] , $arr[$i]);            //TODO 测试发现：如果此处调用，耗时翻倍
            /*if(count($arrFill[$key])){
                $arrFill[$key] = $this->insertSort($arrFill[$key]);
            }*/
        }        //对每个不是空的桶进行排序
        foreach ($arrFill as $key=>$f){            if (count($f)){                $arrFill[$key] = $this->insertSort($f);
            }
        }        //开始从木桶中拿出数据
        for($i = 0; $i < count($arrFill); $i ++)
        {            if($arrFill[$i]){                for($j = 0; $j <= count($arrFill[$i]); $j++)
                {   //这一行主要用来控制输出多个数字
                    if ($arrFill[$i][$j]){                        $arrBucket[] = $arrFill[$i][$j];
                    }
                }
            };
        }        return $arrBucket;
    }

注：

• 上述代码是我根据对木桶排序的定义进行的设计，因为网上多数的PHP代码感觉不合规范，其中的insertSort()为借用的文中所写的插入排序

• 通过测试发现，此方法耗时比countingSort()要长好多，此处仅做参考不做推荐。

总结：

• 当输入的元素是n 个0到k之间的整数时，它的运行时间是 O(n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。

• 稳定的排序方法

• 桶排序是计数排序的升级版

• 最佳情况：T(n) = O(n+k)
  最差情况：T(n) = O(n^2)
  平均情况：T(n) = O(n+k)

附录

【1】Exemple de partage dalgorithmes de tri courants en PHP

【2】自行分析

• 此处提供一个网上多数作为“桶排序”的类似代码段,个人认为并非描述中的排序算法，倒是与文中涉及到的“计数排序”更为契合.

   /**
     * @param $arr 目标数组
     * @return array 返回的已排序数组
     */
    public function bOrCSort($arr)
    {
        $len = count($arr);        $max = max($arr);        if ($len <= 1) {return $arr;}        //填充木桶
        $arrFill = array_fill(0, $max, 0);        for($i = 0; $i < $len ; $i++)
        {            $arrFill[$arr[$i]] ++;
        }        //开始从木桶中拿出数据
        for($i = 0; $i <= $max; $i ++)
        {            for($j = 1; $j <= $arrFill[$i]; $j++)
            { //这一行主要用来控制输出多个数字
                $arrRes[] = $i;
            }
        }        return $arrRes;
    }

【3】用时测试

• 为了简单比较几种算法的用时大小，本人随机生成了数量为10000，数值在300以内的测试数组，文中介绍的算法用时如下：

bucketsort 用时：1013.6640071869 ms
countingSort 用时：5.6858062744141 ms
quick_sort 用时：66540.108919144 ms
selectSort 用时：15234.955072403 ms
bubbleSort 用时：162055.89604378 ms
insertSort 用时：12029.093980789 ms
内置sort 用时：3.0169486999512 ms

• 所以，简单需求的数组排序处理还是建议使用内置的sort()函数.

【4】参考文章

• 十大经典Exemple de partage dalgorithmes de tri courants en PHP（JavaScript描述）【推荐】

• 十大经典排序算法PHP实现教程(注意底部的文章目录)

• PHP 的几种排序算法的比较

【5】提示

• 本文主要为了学习而生

• 累了，就写这些吧

• 如果大家看出错误和意见，希望能给予提醒，共同进步，Thanks …

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!