Algorithme de tri PHP Tri par insertion directe

Cet article présente principalement l'algorithme de tri PHP Straight Insertion Sort (Straight Insertion Sort). Il analyse en détail les principes et les techniques de mise en œuvre de l'algorithme Straight Insertion Sort sous forme d'exemples. Les amis dans le besoin peuvent s'y référer

L'exemple de cet article décrit l'algorithme de tri PHP Straight Insertion Sort. Partagez-le avec tout le monde pour votre référence, les détails sont les suivants :

Introduction à l'algorithme :

Ici, nous en utilisons toujours un de "Dahua Data Structure" Exemple :

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ésultat 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.

Cet article est référencé à partir de "Dahua Data Structure". Il n'est enregistré ici que pour référence future.

Recommandations associées :

Algorithme de tri PHP Shell Sort (Shell Sort)

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!