Tri PHP : idée algorithmique et implémentation de l'algorithme du tri par insertion PHP

Le contenu de cet article concerne le tri PHP : l'idée de l'algorithme et la mise en œuvre de l'algorithme du tri par insertion PHP. Il a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer.

Introduction à l'algorithme :

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

Le poker est quelque chose auquel presque tout le monde d'entre nous a 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 4 dans une liste ordonnée avec deux éléments 3
3 4 5 dans la liste ordonnée de 5 Dans la liste ordonnée de 6
2 3 4 5 6

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

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 de tri par insertion :

// 直接插入排序
function swap(&$arr,$a,$b)
{
$temp    = $arr[$a];
$arr[$a] = $arr[$b];
$arr[$b] = $temp;
}
function insertSort(&$arr)
{
$count = count($arr);
for ($i=1; $i = 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 de l'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)
}

Recommandations associées :

Partage de la méthode de tri des tableaux PHP (tri à bulles, tri par sélection)

php implémente le tri par tas, tutoriel php heap sort_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!