Étapes de mise en œuvre de l'algorithme de tri par insertion en PHP

Étapes de mise en œuvre de l'algorithme de tri par insertion en PHP

Le tri par insertion est un algorithme de tri simple et intuitif. Il construit une séquence ordonnée et insère les données non triées une par une pour obtenir une séquence ordonnée. En PHP, nous pouvons implémenter l'algorithme de tri par insertion en suivant les étapes suivantes.

Étape 1 : Définir une fonction insertionSort, qui reçoit un tableau à trier en paramètre.

function insertionSort($arr) {
  $n = count($arr);
  for ($i = 1; $i < $n; $i++) {
    $key = $arr[$i];
    $j = $i - 1;

    while ($j >= 0 && $arr[$j] > $key) {
      $arr[$j + 1] = $arr[$j];
      $j = $j - 1;
    }
    $arr[$j + 1] = $key;
  }

  return $arr;
}

Étape 2 : Appelez la fonction insertionSort dans le programme principal et transmettez le tableau à trier.

$unsortedArray = [5, 2, 1, 7, 3];
$sortedArray = insertionSort($unsortedArray);

Étape 3 : Définissez une boucle for pour générer le tableau trié.

$n = count($sortedArray);
for ($i = 0; $i < $n; $i++) {
  echo $sortedArray[$i] . " ";
}

Le code complet est le suivant :

Le code ci-dessus implémente l'algorithme de tri par insertion. L'idée principale de l'algorithme est de diviser le tableau à trier en deux parties, triées et non triées, et d'obtenir un résultat ordonné en insérant un par un les éléments non triés dans la partie triée. Dans le code, nous utilisons une boucle for pour parcourir le tableau à trier et insérer l'élément actuel à la position appropriée. La boucle while interne est utilisée pour comparer et déplacer en continu les éléments de la section triée jusqu'à ce que la position appropriée soit trouvée.

La complexité temporelle de l'algorithme de tri par insertion est O(n^2), où n représente la longueur du tableau à trier. Étant donné que l'algorithme implique uniquement des opérations de comparaison et de mouvement d'éléments adjacents, la complexité spatiale est O(1) et il s'agit d'un algorithme de tri sur place.

Résumé : Grâce aux étapes ci-dessus, nous avons implémenté avec succès l'algorithme de tri par insertion en PHP. L'algorithme est simple et efficace et adapté au tri de données à petite échelle. Dans les applications pratiques, si le tableau à trier est grand ou si des performances supérieures sont requises, d'autres algorithmes de tri plus rapides peuvent être envisagés.

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!