Explication détaillée de quatre algorithmes de tri de base en PHP-tutoriel php-php.cn

Explication détaillée de quatre algorithmes de tri de base en PHP

迷茫

Libérer： 2023-03-06 22:32:01

original

1502 Les gens l'ont consulté

par exemple :méthode de tri à bulles, méthode de tri rapide, méthode de tri par sélection, méthode de tri par insertion

1. >Analyse des idées :

Dans un groupe de nombres à trier, pour la séquence qui n'a pas encore été triée, comparer et ajuster les deux nombres adjacents d'avant en arrière, pour que le plus grand nombre descende vers le bas, les plus petits monter vers le haut. Autrement dit, chaque fois que deux nombres adjacents sont comparés et que leur ordre s'avère opposé aux exigences d'ordre, ils sont échangés.

Mise en œuvre du code :

2. Tri par sélection

$arr=array(1,43,54,62,21,66,32,78,36,76,39);  
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;
}

Copier après la connexion

Analyse des idées :

Dans un ensemble de nombres à être triés Parmi eux, sélectionnez le plus petit nombre et échangez-le avec le nombre en première position. Trouvez ensuite le plus petit parmi les nombres restants et échangez-le avec le nombre en deuxième position, et cette boucle continue jusqu'à ce que l'avant-dernier nombre soit comparé au dernier nombre.

Implémentation du code :

3. Tri par insertion

function selectSort($arr) {
//双重循环完成，外层控制轮数，内层控制比较次数
 $len=count($arr);
    for($i=0; $i<$len-1; $i++) {
        //先假设最小的值的位置
        $p = $i;
        for($j=$i+1; $j<$len; $j++) {
            //$arr[$p] 是当前已知的最小值
            if($arr[$p] > $arr[$j]) {
            //比较，发现更小的,记录下最小值的位置；并且在下次比较时采用已知的最小值进行比较。
                $p = $j;
            }
        }
        //已经确定了当前的最小值的位置，保存到$p中。如果发现最小值的位置与当前假设的位置$i不同，则位置互换即可。
        if($p != $i) {
            $tmp = $arr[$p];
            $arr[$p] = $arr[$i];
            $arr[$i] = $tmp;
        }
    }
    //返回最终结果
    return $arr;
}

Copier après la connexion

Analyse des idées :

Dans les éléments à être trié Dans un ensemble de nombres, en supposant que les nombres précédents sont déjà dans l'ordre, il faut maintenant insérer le n-ième nombre dans les nombres ordonnés précédents afin que ces n nombres soient également dans l'ordre. Répétez ce cycle jusqu'à ce que tout soit en ordre.

Implémentation du code :

4. Tri rapide

function insertSort($arr) {
    $len=count($arr); 
    for($i=1, $i<$len; $i++) {
        $tmp = $arr[$i];
        //内层循环控制，比较并插入
        for($j=$i-1;$j>=0;$j--) {
            if($tmp < $arr[$j]) {
                //发现插入的元素要小，交换位置，将后边的元素与前面的元素互换
                $arr[$j+1] = $arr[$j];
                $arr[$j] = $tmp;
            } else {
                //如果碰到不需要移动的元素，由于是已经排序好是数组，则前面的就不需要再次比较了。
                break;
            }
        }
    }
    return $arr;
}

Copier après la connexion

Analyse des idées :

Choisissez un élément de référence. , sélectionne généralement le premier élément ou le dernier élément. Au cours d'un balayage, la colonne à trier est divisée en deux parties, une partie est plus petite que l'élément de référence et l'autre partie est supérieure ou égale à l'élément de référence. A ce moment, l'élément de base est à sa position correcte après le tri, puis les deux parties divisées sont triées récursivement de la même manière.

Mise en œuvre du code :

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!