Exemple de code PHP pour implémenter le tri par insertion

Le contenu de cet article concerne l'exemple de code du tri par insertion en PHP. Il a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer.

C'est tout pour l'algorithme de tri. Tri à bulles, tri rapide, tri par sélection et tri par insertion dans cet article, ces quatre algorithmes sont relativement simples et faciles à comprendre. Les algorithmes plus complexes ne montreront pas leur laideur, afin de ne pas induire les autres en erreur.

Tri par insertion

Tri par insertion (anglais : Insertion Sort) est un algorithme de tri simple et intuitif. Il fonctionne en construisant une séquence ordonnée. Pour les données non triées, il analyse d'arrière en avant dans la séquence triée pour trouver la position correspondante et l'insérer. Dans la mise en œuvre du tri par insertion, le tri sur place est généralement utilisé (c'est-à-dire un tri qui n'utilise que l'espace supplémentaire O(1). Par conséquent, pendant le processus de numérisation d'arrière en avant, il est nécessaire de décaler de manière répétée et progressive le tri par insertion. éléments triés vers l'arrière, fournissant un espace d'insertion pour le dernier élément.

De manière générale, le tri par insertion est implémenté sur les tableaux en utilisant sur place. L'algorithme spécifique est décrit comme suit :

1. En partant du premier élément, l'élément peut être considéré comme ayant été trié

2. Retirez l'élément suivant et procédez de l'envers dans le. séquence d'éléments triés Pré-analyse

3. Si l'élément (trié) est supérieur au nouvel élément, déplacez l'élément à la position suivante

4. Répétez l'étape 3 jusqu'à ce que l'élément trié soit. trouvé inférieur ou égal à La position du nouvel élément

5 Après avoir inséré le nouvel élément dans la position

6. Répétez les étapes 2 à 5

Introduction. de Wikipédia. L'accent est mis sur les étapes 2 à 5.

Démonstration d'animation

Exemple

<?php $arr = [33, 24, 8, 21, 2, 23, 3, 32, 16];

function insertSort($arr)
{
    $count = count($arr);

    if ($count < 2) {
        return $arr;
    }

    for ($i = 1; $i < $count; $i++) {
        // 当前值
        $temp = $arr[$i];
        for ($k = $i - 1; $k >= 0; $k--) {
            // 条件成立，比较值后挪一位，将当前值替换成比较值
            // 倒序 $temp > $arr[$k]
            if ($temp  2 [1] => 3 [2] => 8 [3] => 16 [4] => 21 [5] => 23 [6] => 24 [7] => 32 [8] => 33 )

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!