Analyse de cas de tri par insertion directe PHP

Cette fois, je vais vous présenter une analyse de cas de tri par insertion directe PHP. Quelles sont les précautions pour le tri par insertion directe PHP Voici un cas pratique, jetons un coup d'oeil.

Introduction à l'algorithme :

Le poker est un jeu auquel nous avons presque tous joué. Habituellement, lorsque nous commençons, une personne distribue les cartes, et tout le monde pioche et trie les cartes. Si la première carte que vous piochez est 5 et la deuxième carte est 3, nous insérons naturellement le 3. Allez devant le 5 ; la carte est 4, trouvez-la entre 3 et 5 ; la quatrième carte est 6, placez-la derrière 5 ; la cinquième carte est 2, insérez-la devant 3 ;…. Enfin, lorsque nous avons tiré toutes les cartes, les cartes que nous avons en main sont triées du plus petit au plus grand (points).

Regardons cette séquence :

5 3 3 // Insérer 3 dans une liste ordonnée avec un seul élément 5
3 5 4 4 Insérer 6 dans la liste ordonnée à deux éléments 3 5
3 4 5 6 6 // Insérer 6 dans la liste ordonnée à deux éléments 3 4 5
3 4 5 6 2 2 Dans une liste ordonnée de deux éléments 3 4 5 6
2 3 4 5 6

Idée de base :

L'idée de base du tri par insertion directe est : prendre retirez à chaque fois le premier élément de la liste non ordonnée et insérez-le dans la position appropriée de la liste ordonnée, afin que la liste ordonnée reste en ordre.

Le premier passage compare les deux premiers nombres, puis insère le deuxième nombre dans la liste ordonnée en fonction de la taille ; le deuxième passage analyse les troisièmes données et les deux premiers nombres de l'arrière vers l'avant, et le troisième nombre. est inséré dans la liste ordonnée en fonction de sa taille ; cela se poursuit dans l'ordre et l'ensemble du processus de tri est terminé après (n-1) analyses.

Le tri par insertion directe est composé de deux niveaux de boucles imbriquées. La boucle externe identifie et détermine les valeurs à comparer. La boucle interne détermine la position finale des valeurs à comparer. Le tri par insertion directe compare la valeur à comparer avec sa valeur précédente, de sorte que la boucle externe commence à partir de la deuxième valeur. Si la valeur actuelle est supérieure à la valeur à comparer, la comparaison en boucle se poursuit jusqu'à ce qu'une valeur inférieure à la valeur à comparer soit trouvée et que la valeur à comparer soit placée à la position suivante, mettant ainsi fin au cycle.

La méthode de base du tri par insertion est la suivante : à chaque étape, un enregistrement à trier est inséré à la position appropriée dans la séquence précédemment triée en fonction de la taille de sa clé, jusqu'à ce que tous les enregistrements soient insérés.

Implémentation de l'algorithme :

<?php
//直接插入排序
function swap(array &$arr,$a,$b){
  $temp = $arr[$a];
  $arr[$a] = $arr[$b];
  $arr[$b] = $temp;
}
function InsertSort(array &$arr){
  $count = count($arr);
  //数组中第一个元素作为一个已经存在的有序表
  for($i = 1;$i < $count;$i ++){
    $temp = $arr[$i];   //设置哨兵
    for($j = $i - 1;$j >= 0 && $arr[$j] > $temp;$j --){
      $arr[$j + 1] = $arr[$j];    //记录后移
    }
    $arr[$j + 1] = $temp;   //插入到正确的位置
  }
}
$arr = array(9,1,5,8,3,7,4,6,2);
InsertSort($arr);
var_dump($arr);

Résultats d'exécution :

array(9) {
 [0]=>
 int(1)
 [1]=>
 int(2)
 [2]=>
 int(3)
 [3]=>
 int(4)
 [4]=>
 int(5)
 [5]=>
 int(6)
 [6]=>
 int(7)
 [7]=>
 int(8)
 [8]=>
 int(9)
}

La complexité temporelle de l'algorithme de tri par insertion directe est O(n^2).

Le tri par insertion directe est un tri stable.

Je pense que vous maîtrisez la méthode après avoir lu le cas dans cet article. Pour des informations plus intéressantes, veuillez prêter attention aux autres articles connexes sur le site Web chinois de php !

Lecture recommandée :

Explication détaillée des étapes pour utiliser l'algorithme de tri rapide PHP

Explication détaillée des étapes pour générer des affiches promotionnelles avec PHP

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!