Explication détaillée des algorithmes PHP de base : bouillonnement, sélection, insertion, rapide, fusion

Beaucoup de gens disent que l'algorithme est le cœur du programme. La clé pour savoir si un programme est meilleur que pire est la qualité de l'algorithme. . En tant que PHPer junior, même si je suis peu exposé aux algorithmes. Cependant, vous devez toujours maîtriser les algorithmes de base tels que le tri à bulles, le tri par insertion, le tri par sélection, le tri rapide et le tri par fusion.

Exigences : utilisez le tri à bulles, le tri rapide, le tri par sélection, le tri par insertion et le tri par fusion pour trier les valeurs du tableau ci-dessous de petite à grande.

$arr=tableau(11,3,56, 62,21,66,32,78,36,76,39,88,34);

1. Tri à bulles

Introduction :

Bubble Sort 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 du tableau est répété jusqu'à ce qu'aucun échange ne soit plus nécessaire, ce qui signifie que le tableau a été trié. Le nom de cet algorithme vient du fait que les éléments plus petits « flotteront » lentement vers le haut du tableau grâce à l’échange.

Étapes :

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

2. Faites le même travail pour chaque paire d'éléments adjacents, de la première paire au début à la dernière paire à la fin. À ce stade, le dernier élément doit être le plus grand nombre.

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

4. Continuez à répéter les étapes ci-dessus pour de moins en moins d'éléments à chaque fois jusqu'à ce qu'il n'y ait plus de paires de nombres à comparer.

Code :

<?php $arr = [1, 43, 54, 62, 21, 66, 32, 78, 36, 76, 39, 2];
//Explication détaillée des algorithmes PHP de base : bouillonnement, sélection, insertion, rapide, fusion
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;
}

$arr = bubbleSort($arr);
print_r($arr);

Effet de tri :

2. Tri par sélection

Introduction :

Le tri par sélection est un algorithme de tri simple et intuitif. Voici comment cela fonctionne. Tout d'abord, recherchez le plus petit élément de la séquence non triée et stockez-le au début de la séquence triée. Ensuite, continuez à rechercher le plus petit élément parmi les éléments non triés restants, puis placez-le à la fin de la séquence triée. Et ainsi de suite jusqu'à ce que tous les éléments soient triés.

Code :

<?php $arr = [1, 43, 54, 62, 21, 66, 32, 78, 36, 76, 39, 2];
//Explication détaillée des algorithmes PHP de base : bouillonnement, sélection, insertion, rapide, fusion
//实现思路 双重循环完成，外层控制轮数，当前的最小值。内层控制比较次数
function selectSort($arr) {

    $len = count($arr);

    //$i 当前最小值的位置， 需要参与比较的元素
    for ($i = 0; $i < $len - 1; $i++) {
        //先假设最小的值的位置
        $p = $i;

        //$j 当前都需要和哪些元素比较，$i 后边的。
        for ($j = $i + 1; $j < $len; $j++) {
            //$arr[$p] 是 当前已知的最小值
            //比较，发现更小的,记录下最小值的位置；并且在下次比较时，应该采用已知的最小值进行比较。
            $p = ($arr[$p] <= $arr[$j]) ? $p : $j;
        }

        //已经确定了当前的最小值的位置，保存到$p中。
        //如果发现 最小值的位置与当前假设的位置$i不同，则位置互换即可
        if ($p != $i) {
            $tmp     = $arr[$p];
            $arr[$p] = $arr[$i];
            $arr[$i] = $tmp;
        }
    }
    //返回最终结果
    return $arr;
}

$arr = selectSort($arr);
print_r($arr);

3. 🎜>

Introduction :

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 parcourt la séquence triée d'avant en arrière, trouve la position correspondante et l'insère. Dans la mise en œuvre du tri par insertion, le tri sur place est généralement utilisé (c'est-à-dire un tri qui utilise uniquement l'espace supplémentaire O(1). Par conséquent, pendant le processus d'analyse d'arrière en avant, les éléments triés doivent être triés de manière répétée et progressive). décalé vers l'arrière, fournissant un espace d'insertion pour le dernier élément.

Étapes :

1. En partant du premier élément, l'élément peut être considéré comme ayant été trié

2. , dans Scannez la séquence d'éléments triés d'arrière en avant

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

4. , Jusqu'à ce que la position où l'élément trié est inférieur ou égal au nouvel élément soit trouvée

5. Insérez le nouvel élément dans la position

6. >

code :

<?php $arr = [1, 43, 54, 62, 21, 66, 32, 78, 36, 76, 39,2];
//插入排序
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+1] = $arr[$j];

                //将前面的数设置为 当前需要交换的数
                $arr[$j] = $tmp;
            } else {
                //如果碰到不需要移动的元素
                //由于是已经排序好是数组，则前面的就不需要再次比较了。
                break;
            }
        }
    }
    //将这个元素 插入到已经排序好的序列内。
    //返回
    return $arr;
}

$arr = insert_sort($arr);
print_r($arr);

4. Tri rapide

Introduction :

Explication détaillée des algorithmes PHP de base : bouillonnement, sélection, insertion, rapide, fusion是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，Explication détaillée des algorithmes PHP de base : bouillonnement, sélection, insertion, rapide, fusion通常明显比其他Ο(n log n) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来，且在大部分真实世界的数据，可以决定设计的选择，减少所需时间的二次方项之可能性。

步骤：

1、从数列中挑出一个元素，称为 “基准”（pivot），

2、重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。

3、递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

代码：

<?php $arr = [1, 43, 54, 62, 21, 66, 32, 78, 36, 76, 39,2];
//Explication détaillée des algorithmes PHP de base : bouillonnement, sélection, insertion, rapide, fusion
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);
}

$arr = quick_sort($arr);
print_r($arr);

排序效果：

5、Explication détaillée des algorithmes PHP de base : bouillonnement, sélection, insertion, rapide, fusion

利用递归，先拆分、后合并、再排序。

步骤:

• 均分数列为两个子数列
• 递归重复上一步骤，直到子数列只有一个元素
• 父数列合并两个子数列并排序，递归返回数列

代码：

<?php $arr = [1, 43, 54, 62, 21, 66, 32, 78, 36, 76, 39,2];

// Explication détaillée des algorithmes PHP de base : bouillonnement, sélection, insertion, rapide, fusion主程序
function mergeSort($arr) {
    $len = count($arr);

    // 递归结束条件, 到达这步的时候, 数组就只剩下一个元素了, 也就是分离了数组
    if ($len <= 1) {
        return $arr;
    }

    $mid  = intval($len / 2);             // 取数组中间
    $left = array_slice($arr, 0, $mid); // 拆分数组0-mid这部分给左边left
    $right= array_slice($arr, $mid);          // 拆分数组mid-末尾这部分给右边right
    $left = mergeSort($left);                 // 左边拆分完后开始递归合并往上走
    $right= mergeSort($right);                // 右边拆分完毕开始递归往上走
    $arr  = merge($left, $right);             // 合并两个数组,继续递归

    return $arr;
}

// merge函数将指定的两个有序数组(arrA, arr)合并并且排序
function merge($arrA, $arrB) {
    $arrC = array();
    while (count($arrA) && count($arrB)) {
        // 这里不断的判断哪个值小, 就将小的值给到arrC, 但是到最后肯定要剩下几个值,
        // 不是剩下arrA里面的就是剩下arrB里面的而且这几个有序的值, 肯定比arrC里面所有的值都大所以使用
        //从小到大 < || 从大到小 >
        $arrC[] = $arrA[0] <p>排序效果：</p><p> </p><p><img src="https://img.php.cn/upload/article/000/000/024/4059d12f5632ac9f990ed52b74747d4b-4.gif" alt="Explication détaillée des algorithmes PHP de base : bouillonnement, sélection, insertion, rapide, fusion"    style="max-width:90%"  style="max-width:90%"></p><p>相关推荐：<a href="https://www.php.cn/" target="_blank">PHP教程</a><br></p>

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!